Submission #154231

#	Time	Username	Problem	Language	Result	Execution time	Memory
154231		Ruxandra985	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	318 ms	18424 KiB

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 (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: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 / 160