제출 #1062494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062494		new_acc	슈퍼트리 잇기 (IOI20_supertrees)	C++14	100 / 100	150 ms	24148 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N=1e4+10;
int fau[N],fau2[N];
bool vis[N];
vi kt[N];
int Find(int a){
    if(fau[a]==a) return a;
    return fau[a]=Find(fau[a]);
}
void Union(int a,int b){
    a=Find(a),b=Find(b);
    fau[a]=b;
}
int Find2(int a){
    if(fau2[a]==a) return a;
    return fau2[a]=Find2(fau2[a]);
}
void Union2(int a,int b){
    a=Find2(a),b=Find2(b);
    fau2[a]=fau2[b];
}
int construct(vector<vi> g) {
    int n=g.size();
    iota(fau,fau+1+n,0);
    iota(fau2,fau2+1+n,0);
    vector<vi> ans=g;
    for(int i=0;i<n;i++){
        for(int i2=0;i2<n;i2++) ans[i][i2]=0;
    }
    for(int i=0;i<n;i++){
        for(int i2=0;i2<n;i2++){
            if(g[i][i2]==1) Union(i+1,i2+1);
        }
    } 
    for(int i=0;i<n;i++){
        for(int i2=0;i2<n;i2++){
            if(g[i][i2]==2) Union2(Find(i+1),Find(i2+1));
        }
    }
    for(int i=1;i<=n;i++){
        int u=Find(i);               
        if(vis[u]) continue;
        vis[u]=1;
        kt[Find2(u)].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(kt[i].size()==2){
            return 0;
        }
        if(kt[i].size()<2) continue;
        for(int i2=0;i2<(int)kt[i].size();i2++){
            int nxt=kt[i][(i2+1)%kt[i].size()],u=kt[i][i2];
            ans[u-1][nxt-1]=1,ans[nxt-1][u-1]=1;
        }
    }
    for(int i=1;i<=n;i++){
        int u=Find(i);
        if(u!=i) ans[u-1][i-1]=1,ans[i-1][u-1]=1;
    }
    for(int i=0;i<n;i++){
        for(int i2=0;i2<n;i2++){
            int u=Find(i+1),u2=Find(i2+1);
            int v1=Find2(u),v2=Find2(u2);
            if(g[i][i2]==0){
                if(u==u2 or v1==v2) return 0;
            }
            if(g[i][i2]==1){
                if(u!=u2) return 0;
            }
            if(g[i][i2]==2){
                if(u==u2 or v1!=v2) return 0;
            }
            if(g[i][i2]==3) return 0;
        }
    }
    build(ans);
	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4