Submission #154189

#	Time	Username	Problem	Language	Result	Execution time	Memory
154189		Ruxandra985	Uzastopni (COCI15_uzastopni)	C++14	120 / 160	1084 ms	17864 KiB

uzastopni

#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 = joke[nod] + 1; x<=k;x++)
            dp[nod][x] |= dp[vecin][x];
            //for (y=x;y<=k;y++)
              //   dp[nod][x][y] = (dp[nod][x][y] | dp[vecin][x][y]);
        for (x=1;x<joke[nod];x++)
            for (y=x;y<joke[nod];y++)
                 dp[nod][x][y] = (dp[nod][x][y] | dp[vecin][x][y]);

    }
    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++)
        for (j=joke[1];j<=k;j++){
            sol = sol + dp[1][i][j];
        }
    fprintf (fout,"%d",sol);
    return 0;
}

Compilation message (stderr)

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:49: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:51: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:55: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: 120 / 160