Submission #1271790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271790		mfong_123abc	Unique Cities (JOI19_ho_t5)	C++20	4 / 100	1822 ms	9944 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;

int n,m,v1,v2,c[102100],dist[102100];
vector<int> adj[202100];
bool vis[4000], b2[4000];
int b[4000], cnt[4000];

int search(int st){
    int ans=0;
    fill(cnt+1, cnt+1+n ,0); fill(vis+1, vis+1+n, false); fill(b2+1, b2+1+n, 0);
    queue<pair<int,int> > bfs;
    bfs.push({st,0});
    vis[st]=true;
    while(!bfs.empty()){
        int v=bfs.front().first, cd=bfs.front().second;
        // cout<<st<<" "<<v<<" "<<cd<<"\n";
        dist[v]=cd;
        bfs.pop();
        cnt[cd]++; b[cd]=v;
        for(auto v3: adj[v]){
            if(vis[v3])continue; vis[v3]=1;
            bfs.push({v3, cd+1});
        }
    }
    for(int i=1;i<=n;i++){
        if(cnt[i]==1){
            b2[c[b[i]]]=true;
        }
    }
    for(int i=1;i<=n;i++)ans+=b2[i];
    return ans;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        cin>>v1>>v2;
        adj[v1].push_back(v2); adj[v2].push_back(v1);
    }
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++)cout<<search(i)<<"\n";
}

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