Submission #98584

#	Time	Username	Problem	Language	Result	Execution time	Memory
98584		JohnTitor	Uzastopni (COCI15_uzastopni)	C++11	160 / 160	36 ms	24704 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
using ll=long long;
using ld=long double;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "UZASTOPNI"
int n;
int c[10001];
vector <int> g[10001];
bitset <101> f[10001];
void dfs(int u){
    for(int v: g[u]) dfs(v);
    f[u][c[u]]=1;
    vector <bitset<101>> a[101];
    for(int v: g[u]) if(c[v]>c[u]){
        bitset<101> temp;
        FOR(i, c[v], 100) temp[i]=f[v][i];
        FOR(i, c[u]+1, c[v]) if(f[v][i]) a[i].pb(temp);
    }
    else if(c[v]<c[u]){
        bitset<101> temp;
        FOR(i, 1, c[v]) temp[i]=f[v][i];
        DFOR(i, c[u]-1, c[v]) if(f[v][i]) a[i].pb(temp);
    }
    FFOR(i, c[u], 100) if(f[u][i]) for(auto &x: a[i+1]) f[u]|=x;
    DFOR(i, c[u], 2) if(f[u][i]) for(auto &x: a[i-1]) f[u]|=x;
}
int main(){
    #ifdef Uiharu
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Uiharu
    read(n);
    FOR(i, 1, n) read(c[i]);
    FFOR(i, 1, n){
        int u, v;
        read(u);
        read(v);
        g[u].pb(v);
    }
    dfs(1);
    int cnt_left=1;
    int cnt_right=1;
    FFOR(i, 1, c[1]) cnt_left+=f[1][i];
    FOR(i, c[1]+1, 100) cnt_right+=f[1][i];
    writeln(cnt_left*cnt_right);
}

• Subtask 1: 160 / 160