제출 #707764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707764		victor_gao	Mergers (JOI19_mergers)	C++17	56 / 100	3061 ms	40456 KiB

mergers

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 500015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct DSU{
    int boss[N],sz[N],group=0;
    void init(int n){
        group=n;
        for (int i=0;i<=n+1;i++){
            boss[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        if (boss[x]==x) return x;
        return boss[x]=find(boss[x]);
    }
    void Merge(int a,int b){
        int ra=find(a),rb=find(b);
        if (ra==rb) return;
        group--;
        if (sz[ra]<sz[rb]) swap(ra,rb);
        sz[ra]+=sz[rb];
        boss[rb]=ra;
    }
}d;
int n,k,fa[N],dep[N],is[N],deg[N],cnt=0;
vector<int>g[N],all[N];
void dfs(int p,int lp){
    fa[p]=lp; dep[p]=dep[lp]+1;
    for (auto i:g[p]){
        if (i!=lp)
            dfs(i,p);
    }
}
void merge_path(int a,int b){
    vector<int>path;
  //  cout<<"Go "<<a<<" "<<b<<'\n';
    while (a!=b){
        if (dep[a]>=dep[b]){
            path.push_back(a);
            d.Merge(is[a],is[fa[a]]);
            a=fa[a];
        }
        else {
            path.push_back(b);
            d.Merge(is[b],is[fa[b]]);
            b=fa[b];
        }
    }
    /*
    cout<<"path : ";
    for (auto i:path){
        cout<<i<<" ";
        fa[i]=a;
    }
    cout<<a<<'\n';
    */
}
signed main(){
    fast
    cin>>n>>k;
    d.init(k);
    vector<pii>edge;
    for (int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
        edge.push_back({a,b});
    }
    for (int i=1;i<=n;i++){
        cin>>is[i];
        all[is[i]].push_back(i);
    }
    dfs(1,1);
    for (int i=1;i<=k;i++){
        for (int j=1;j<all[i].size();j++)
            merge_path(all[i][j-1],all[i][j]);
    }
    for (auto i:edge){
        if (d.find(is[i.x])!=d.find(is[i.y])){
            deg[d.find(is[i.x])]++;
            deg[d.find(is[i.y])]++;
        }
    }
    for (int i=1;i<=k;i++)
        cnt+=(deg[i]==1);
    cout<<(cnt+1)/2<<'\n';
}

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp: In function 'int main()':
mergers.cpp:89:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int j=1;j<all[i].size();j++)
      |                      ~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 0 / 14
• Subtask 4: 22 / 22
• Subtask 5: 0 / 30