Submission #154219

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
154219	2019-09-19T11:26:10 Z	Ruxandra985	Uzastopni (COCI15_uzastopni)	C++14	48 / 160	500 ms	17528 KB

uzastopni

#include <cstdio>
#include <iostream>
#include <vector>
#include <bitset>

using namespace std;
bitset <101> dp[10001][101];
bitset <101> aux[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];
    }
    for (i=1;i<=k;i++)
        aux[i].reset();
    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++){
            for (y=x;y<=k;y++){
                if (x <= joke[vecin] && joke[vecin] <= y){
                    if (x > joke[nod] || y < joke[nod])
                        dp[nod][x][y] = (dp[nod][x][y] | dp[vecin][x][y]);
                }
                aux[y][x-1] = (aux[y][x-1] | dp[nod][x][y]);
            }
        }

    }
    for (len = 2; len <= k ;len++){
        for (x = 1; x + len - 1 <= k ; x++){
            y = x + len - 1;
            if ((dp[nod][x] & aux[y]).count())
                dp[nod][x][y] = 1;
            //for (z=x;z<y && !dp[nod][x][y];z++){
              //  dp[nod][x][y] = (dp[nod][x][z] & dp[nod][z+1][y]);
            //}
        }
    }



}
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++)
        for (j=joke[1];j<=k;j++){
            //if (dp[1][i][j])
              //  printf ("%d %d\n",i,j);
            sol = sol + dp[1][i][j];
        }
    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:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
uzastopni.cpp:12:21: warning: unused variable 'z' [-Wunused-variable]
     int i,vecin,x,y,z,len;
                     ^
uzastopni.cpp: In function 'int main()':
uzastopni.cpp:54: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:56: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:60: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

48.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	632 KB	Output isn't correct
2	Correct	5 ms	632 KB	Output is correct
3	Correct	4 ms	760 KB	Output is correct
4	Correct	3 ms	636 KB	Output is correct
5	Correct	5 ms	760 KB	Output is correct
6	Execution timed out	1070 ms	772 KB	Time limit exceeded
7	Execution timed out	1076 ms	744 KB	Time limit exceeded
8	Execution timed out	1051 ms	732 KB	Time limit exceeded
9	Correct	185 ms	720 KB	Output is correct
10	Correct	233 ms	848 KB	Output is correct
11	Execution timed out	1042 ms	8144 KB	Time limit exceeded
12	Execution timed out	1053 ms	8020 KB	Time limit exceeded
13	Execution timed out	1076 ms	12612 KB	Time limit exceeded
14	Execution timed out	1076 ms	17528 KB	Time limit exceeded
15	Execution timed out	1076 ms	17528 KB	Time limit exceeded
16	Execution timed out	1078 ms	17528 KB	Time limit exceeded
17	Execution timed out	1088 ms	12548 KB	Time limit exceeded
18	Execution timed out	1086 ms	13056 KB	Time limit exceeded
19	Execution timed out	1068 ms	3064 KB	Time limit exceeded
20	Execution timed out	1063 ms	4792 KB	Time limit exceeded