oj.uz

Submission #154190

# Submission time Handle Problem Language Result Execution time Memory
154190 2019-09-18T19:03:50 Z Ruxandra985 Uzastopni (COCI15_uzastopni) C++14
0 / 160
 500 ms 17732 KB 
#include <cstdio>
#include <iostream>
#include <vector>
#include <bitset>

using namespace std;
bitset <101> dp[10001][101];
vector <int> v[10001];
int joke[10001],k;
void dfs (int nod){
    int i,vecin,x,y,z,len;
    dp[nod][joke[nod]][joke[nod]] = 1;

    for (i=0;i<v[nod].size();i++){
        dfs (v[nod][i]);
        vecin = v[nod][i];
        /// acum e acum:P
        for (x = 1; x<=k;x++) /// daca le as pune pe toate
            dp[nod][x] |= dp[vecin][x];

    }
     for (x=1;x<=joke[nod];x++)
        for (y=joke[nod];y<=k;y++)
            dp[nod][x][y] = 0;

    for (len = 2; len <= k ;len++){
        for (x = 1; x + len - 1 <= k ; x++){
            y = x + len - 1;
            for (z=x;z<y && !dp[nod][x][y];z++){
                dp[nod][x][y] = (dp[nod][x][z] & dp[nod][z+1][y]);
            }
        }
    }
    for (x = joke[nod] + 1; x<=k;x++)
        dp[nod][x].reset();
    for (x=1;x<joke[nod];x++)
        for (y=x;y<joke[nod];y++)
            dp[nod][x][y] = 0;



}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n,i,x,y,sol,j;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++){
        fscanf (fin,"%d",&joke[i]);
        k = max ( k ,joke[i]);
    }
    for (i=1;i<n;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
    }
    dfs (1);
    sol = 0;
    for (i=1;i<=joke[1];i++)
        sol = sol + dp[1][i].count();
    fprintf (fout,"%d",sol);
    return 0;
}

Compilation message

uzastopni.cpp: In function 'void dfs(int)':
uzastopni.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
uzastopni.cpp: In function 'int main()':
uzastopni.cpp:47:21: warning: unused variable 'j' [-Wunused-variable]
     int n,i,x,y,sol,j;
                     ^
uzastopni.cpp:48:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&n);
     ~~~~~~~^~~~~~~~~~~~~
uzastopni.cpp:50:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&joke[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~
uzastopni.cpp:54:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Incorrect 3 ms 632 KB Output isn't correct
3 Incorrect 3 ms 760 KB Output isn't correct
4 Incorrect 3 ms 760 KB Output isn't correct
5 Incorrect 3 ms 760 KB Output isn't correct
6 Incorrect 46 ms 800 KB Output isn't correct
7 Incorrect 46 ms 760 KB Output isn't correct
8 Incorrect 46 ms 776 KB Output isn't correct
9 Incorrect 45 ms 680 KB Output isn't correct
10 Incorrect 44 ms 760 KB Output isn't correct
11 Incorrect 42 ms 16760 KB Output isn't correct
12 Incorrect 29 ms 16760 KB Output isn't correct
13 Incorrect 22 ms 16632 KB Output isn't correct
14 Execution timed out 1074 ms 17644 KB Time limit exceeded
15 Execution timed out 1062 ms 17732 KB Time limit exceeded
16 Execution timed out 1081 ms 17656 KB Time limit exceeded
17 Incorrect 21 ms 16760 KB Output isn't correct
18 Incorrect 22 ms 16760 KB Output isn't correct
19 Execution timed out 1077 ms 4812 KB Time limit exceeded
20 Execution timed out 1085 ms 4988 KB Time limit exceeded