Submission #1139120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139120		Otalp	Unique Cities (JOI19_ho_t5)	C++20	0 / 100	431 ms	14260 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define unm unordered_map

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const int MAXA = 2e5 + 5;

int a[200100], o[200100];
vector<int> q[200100];

struct node{
    unm<int, int> cnt;
    int res=0;
    node(){
        cnt.clear();
    }
};


node *d[200100];


// void un(node &a, node &b){
//     for(pii g: b.cnt){
//         int x = g.ff + 1;
//         if(a.cnt[x] == 1) a.dp -= 1;
//         a.cnt[x] += g.ss;
//         if(a.cnt[x] == 1) a.dp += 1;
//     }  
// }

// void dv(node &a, node &b){
//     for(pii g: b.cnt){
//         int x = g.ff + 1;
//         if(a.cnt[x] == 1) a.dp -= 1;
//         a.cnt[x] -= g.ss;
//         if(a.cnt[x] == 1) a.dp += 1;
//     }
// }

int pos[200100], sz[200100], pc[200100];

// void ddfs0(int v, int p, int k){
//     sz[v] = 1;
//     for(int to: q[v]){
//         if(pos[to] or to == p) continue;
//         ddfs0(to, v, k + 1);
//         sz[v] += sz[to];
//     }
// }

void dfs0(int v, int p, int k){
    sz[v] = 1;
    o[v] = k;
    for(int to: q[v]){
        if(pos[to] or to == p) continue;
        dfs0(to, v, k + 1);
        sz[v] += sz[to];
    }
} 

int findc(int v, int p, int k){
    pc[v] = 1;
    for(int to: q[v]){
        if(to == p or pos[to]) continue;
        if(sz[to] > k/2) return findc(to, v, k);
    }
    pc[v] = 0;
    return v;
}

void add(int v, int p, int k, node *t, int u){
    if(t -> cnt[k-u] == 1) t -> res --;
    t -> cnt[k-u] ++;
    if(t -> cnt[k-u] == 1) t -> res ++;
    for(int to: q[v]){
        if(to == p or pos[to]) continue;
        add(to, v, k + 1, t, u);
    }
}

void sub(int v, int p, int k, node *t, int u){
    if(t -> cnt[k-u] == 1) t -> res --;
    t -> cnt[k-u] --;
    if(t -> cnt[k-u] == 1) t -> res ++;
    for(int to: q[v]){
        if(to == p or pos[to]) continue;
        sub(to, v, k + 1, t, u);
    }
}



int res[200100];

void dfs2(int v, int p, node *t, int k){
    pos[v] = 1;
    int dto = -1;
    for(int to: q[v]){
        if(to == p or pos[to]) continue;
        add(to, 0, 1, t, k);
        if(pc[to]) dto = to;
    }
    if(t -> cnt[-k] == 1) t -> res --;
    res[v] = t -> res;
    // cout<<"################";
    // cout<<v<<' '<<k<<' '<<dto<<'\n';
    // for(pii g: t -> cnt){
    //     cout<<g.ff + k<<' '<<g.ss<<'\n';
    // }
    t -> cnt[-k] ++;
    if(t -> cnt[-k] == 1) t -> res ++;
    for(int to: q[v]){
        if(to == p or pos[to] or to == dto) continue;
        sub(to, 0, 1, t, k);
        dfs0(to, 0, 1);
        int c = findc(to, 0, sz[to]);
        dfs2(c, v, t, k+o[c]); 
        add(to, 0, 1, t, k);
    }
    if(t -> cnt[-k] == 1) t -> res --;
    t -> cnt[-k] --;
    if(t -> cnt[-k] == 1) t -> res ++;
    for(int to: q[v]){
        if(to == p or pos[to]) continue;
        sub(to, 0, 1, t, k);
    }

    if(dto != -1){
        dfs0(dto, 0, 1);
        int to = dto;
        int c =  findc(to, 0, sz[to]);
        if(t -> cnt[-k+2*o[c]] == 1) t -> res --;
        t -> cnt[-k+2*o[c]] ++;
        if(t -> cnt[-k+2*o[c]] == 1) t -> res ++;
        for(int to: q[v]){
            if(to == p or pos[to] or to == dto) continue;
            add(to, 0, 1, t, k-2*o[c]);
        }
        dfs2(c, v, t, k-o[c]);
        for(int to: q[v]){
            if(to == p or pos[to] or to == dto) continue;
            sub(to, 0, 1, t, k-2*o[c]);
        }
        if(t -> cnt[-k+2*o[c]] == 1) t -> res --;
        t -> cnt[-k+2*o[c]] --;
        if(t -> cnt[-k+2*o[c]] == 1) t -> res ++;
    }

    pos[v] = 0;
}

void solve(){
    int n, m;
    cin>>n>>m;
    for(int i=1; i<n; i++){
        int l, r;
        cin>>l>>r;
        q[l].pb(r);
        q[r].pb(l);
    }
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    dfs0(1, 0, 0);
    int c = findc(1, 0, sz[1]);
    for(int i=1; i<=n; i++) pc[i] = 0;
    // dfs1(c, 0);
    // ddfs0(c, 0, 0);
    node *t = new node();
    dfs2(c, 0, t, 0);
    // cout<<d[c] -> res;
    for(int i=1; i<=n; i++){
        cout<<(res[i] >= 1)<<'\n';
    }
    // for(pii g: t -> cnt) cout<<g.ff<<' '<<g.ss<<'\n';
}

int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout<<'\n';
    }
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32