Submission #154231

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
154231	2019-09-19T11:47:02 Z	Ruxandra985	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	318 ms	18424 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++){
        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][y] && (dp[nod][x] & aux[y]).any()){
                dp[nod][x][y] = 1;
                aux[y][x-1] = 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:55: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:57: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:61: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

160.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	3 ms	632 KB	Output is correct
3	Correct	2 ms	632 KB	Output is correct
4	Correct	3 ms	760 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	6 ms	760 KB	Output is correct
7	Correct	6 ms	808 KB	Output is correct
8	Correct	5 ms	764 KB	Output is correct
9	Correct	5 ms	764 KB	Output is correct
10	Correct	5 ms	760 KB	Output is correct
11	Correct	31 ms	16632 KB	Output is correct
12	Correct	26 ms	16632 KB	Output is correct
13	Correct	22 ms	16636 KB	Output is correct
14	Correct	316 ms	18384 KB	Output is correct
15	Correct	315 ms	18424 KB	Output is correct
16	Correct	318 ms	18356 KB	Output is correct
17	Correct	23 ms	16632 KB	Output is correct
18	Correct	23 ms	16760 KB	Output is correct
19	Correct	316 ms	16632 KB	Output is correct
20	Correct	317 ms	16528 KB	Output is correct