Submission #154153

#	Time	Username	Problem	Language	Result	Execution time	Memory
154153		Ruxandra985	Uzastopni (COCI15_uzastopni)	C++14	120 / 160	1088 ms	9080 KiB

uzastopni

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

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

    for (i=0;i<v[nod].size();i++){
        dfs (v[nod][i]);
        vecin = v[nod][i];
        /// acum e acum:P
        if (joke[vecin]!=joke[nod])
            dp[joke[vecin]][joke[vecin]][nod] = 1;
        for (x = 1; x <= k ;x ++)
            for (y = x ;y <= k ; y++){
                if (x > joke[nod] || y < joke[nod])
                    dp[x][y][nod] = (dp[x][y][nod] | dp[x][y][vecin]);
            }

    }
    for (len = 2; len <= k ;len++){
        for (x = 1; x + len - 1 <= k ; x++){
            y = x + len - 1;
            for (z=x;z<y && !dp[x][y][nod];z++){
                dp[x][y][nod] = (dp[x][z][nod] & dp[z+1][y][nod]);
            }
        }
    }
    for (x=1;x<=k;x++){
        for (y=x;y<=k;y++){
            if (x > joke[nod] || y < joke[nod])
                dp[x][y][nod] = 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[i][j][1];
        }
    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