Submission #154218

#	Time	Username	Problem	Language	Result	Execution time	Memory
154218		Ruxandra985	Uzastopni (COCI15_uzastopni)	C++14	120 / 160	1079 ms	17976 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=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]);
                }
            }
        }

    }

    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]);
            }
        }
    }



}
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:46: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:48: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:52: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