oj.uz

답안 #991893

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991893 2024-06-03T10:37:53 Z MarwenElarbi Mergers (JOI19_mergers) C++17
0 / 100
 138 ms 73672 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<<" "<<adj2[x].size()<<endl;
    if(adj2[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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 57180 KB Output is correct
2 Correct 12 ms 57152 KB Output is correct
3 Correct 14 ms 57180 KB Output is correct
4 Correct 14 ms 57180 KB Output is correct
5 Correct 13 ms 57132 KB Output is correct
6 Correct 14 ms 57180 KB Output is correct
7 Correct 12 ms 57184 KB Output is correct
8 Correct 14 ms 57180 KB Output is correct
9 Correct 13 ms 57180 KB Output is correct
10 Correct 15 ms 57164 KB Output is correct
11 Correct 13 ms 57180 KB Output is correct
12 Correct 13 ms 57180 KB Output is correct
13 Correct 14 ms 57180 KB Output is correct
14 Incorrect 14 ms 57196 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 57180 KB Output is correct
2 Correct 12 ms 57152 KB Output is correct
3 Correct 14 ms 57180 KB Output is correct
4 Correct 14 ms 57180 KB Output is correct
5 Correct 13 ms 57132 KB Output is correct
6 Correct 14 ms 57180 KB Output is correct
7 Correct 12 ms 57184 KB Output is correct
8 Correct 14 ms 57180 KB Output is correct
9 Correct 13 ms 57180 KB Output is correct
10 Correct 15 ms 57164 KB Output is correct
11 Correct 13 ms 57180 KB Output is correct
12 Correct 13 ms 57180 KB Output is correct
13 Correct 14 ms 57180 KB Output is correct
14 Incorrect 14 ms 57196 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 57180 KB Output is correct
2 Correct 12 ms 57152 KB Output is correct
3 Correct 14 ms 57180 KB Output is correct
4 Correct 14 ms 57180 KB Output is correct
5 Correct 13 ms 57132 KB Output is correct
6 Correct 14 ms 57180 KB Output is correct
7 Correct 12 ms 57184 KB Output is correct
8 Correct 14 ms 57180 KB Output is correct
9 Correct 13 ms 57180 KB Output is correct
10 Correct 15 ms 57164 KB Output is correct
11 Correct 13 ms 57180 KB Output is correct
12 Correct 13 ms 57180 KB Output is correct
13 Correct 14 ms 57180 KB Output is correct
14 Incorrect 14 ms 57196 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 65352 KB Output is correct
2 Incorrect 138 ms 73672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 57180 KB Output is correct
2 Correct 12 ms 57152 KB Output is correct
3 Correct 14 ms 57180 KB Output is correct
4 Correct 14 ms 57180 KB Output is correct
5 Correct 13 ms 57132 KB Output is correct
6 Correct 14 ms 57180 KB Output is correct
7 Correct 12 ms 57184 KB Output is correct
8 Correct 14 ms 57180 KB Output is correct
9 Correct 13 ms 57180 KB Output is correct
10 Correct 15 ms 57164 KB Output is correct
11 Correct 13 ms 57180 KB Output is correct
12 Correct 13 ms 57180 KB Output is correct
13 Correct 14 ms 57180 KB Output is correct
14 Incorrect 14 ms 57196 KB Output isn't correct
15 Halted 0 ms 0 KB -