oj.uz

Submission #991889

# Submission time Handle Problem Language Result Execution time Memory
991889 2024-06-03T10:33:40 Z MarwenElarbi Mergers (JOI19_mergers) C++17
0 / 100
 134 ms 73692 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=5e5+5;
vector<int> adj[nax];
set<int> stl[nax];
vector<int> sz(nax);
vector<int> sum(nax);
vector<int> s(nax);
vector<int> colours(nax);
int ans=0;
vector<int> parent(nax);
vector<int> adj2[nax];
vector<bool> vis(nax);
int find(int x){
    if(parent[x]==x) return x;
    return parent[x]=find(parent[x]);
}
bool sameset(int x,int y){
    return find(x)==find(y);
}
void joinset(int x,int y){
    x=find(x);
    y=find(y);
    parent[x]=y;
}
void precompute(int x,int p){
    stl[x].insert(s[x]);
    sum[x]=colours[s[x]];
    sz[x]=1;
    for(auto u:adj[x]){
        if(u==p) continue;
        precompute(u,x);
        sz[x]+=sz[u];
        if(stl[u].size()>stl[x].size()){
            sum[x]=sum[u];
            swap(stl[u],stl[x]);
        }    
        for(auto i:stl[u]){
            if(stl[x].count(i)) continue;
            stl[x].insert(i);
            sum[x]+=colours[i];
        }
    }
    if(p!=-1&&sum[x]>sz[x]){
        joinset(x,p);
    }
}
void nab(int x,int p){
    for(auto u:adj[x]){
        if(u==p) continue;
        if(!sameset(x,u)){
            int curx=find(x);
            int cury=find(u);
            adj2[curx].pb(cury);
            adj2[cury].pb(curx);
        }
        nab(u,x);
    }
}
void dfs(int x,int p){
    //cout <<x<<endl;
    if(adj[x].size()==1) ans++;
    for(auto u:adj2[x]){
        if(u==p) continue;
        dfs(u,x);
    }
    return;
}
int main() {
    int n,k;
    cin>>n>>k;
    for (int i = 0; i < n-1; ++i)
    {
        int a,b;
        cin>>a>>b;
        a--;b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for (int i = 0; i < n; ++i)
    {
        parent[i]=i;
    }
    for (int i = 0; i < n; ++i)
    {
        cin>>s[i];
        s[i]--;
        colours[s[i]]++;
    }
    precompute(0,-1);
    nab(0,-1);
    for (int i = 0; i < n; ++i)
    {
        if(adj2[i].size()>0){
            dfs(i,-1);
            break;
        }
    }
    cout <<ans/2<<endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 57176 KB Output is correct
2 Incorrect 11 ms 57180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 57176 KB Output is correct
2 Incorrect 11 ms 57180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 57176 KB Output is correct
2 Incorrect 11 ms 57180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 65360 KB Output is correct
2 Incorrect 134 ms 73692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 57176 KB Output is correct
2 Incorrect 11 ms 57180 KB Output isn't correct
3 Halted 0 ms 0 KB -