Submission #1137621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137621		Otalp	Unique Cities (JOI19_ho_t5)	C++20	4 / 100	2095 ms	12028 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 cnt[200100], a[200100], dp[200100];
vector<int> q[200100];

void dfs(int v, int p, int k){
    if(cnt[k] != 0){
        cnt[k] = -1;
    }
    else{
        cnt[k] = a[v];
    }
    for(auto to: q[v]){
        if(to == p) continue;
        dfs(to, v, k + 1);
    }
}

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];
    }
    for(int v=1; v<=n; v++){
        for(int i=1; i<=n; i++){
            cnt[i] = 0;
            dp[i] = 0;
        }
        dfs(v, 0, 0);
        int ans = 0;
        for(int i=1; i<=n; i++){
            if(cnt[i] > 0){
                ans -= dp[cnt[i]];
                dp[cnt[i]] = 1;
                ans ++;
            }
        }
        cout<<ans<<'\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: 4 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32