제출 #768430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
768430		Khizri	슈퍼트리 잇기 (IOI20_supertrees)	C++17	11 / 100	179 ms	36044 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=1e3+5;
int n,color[mxn],k,color2[mxn],sz,lst,arr[mxn][mxn];
vector<int>vt[mxn];
vector<int>vt2[mxn];
vector<vector<int>>p;
void dfs(int u){
    color[u]=k;
    sz++;
    for(int v:vt[u]){
        if(!color[v]){
            arr[u][v]=1;
            arr[v][u]=1;
            dfs(v);
        }
    }
}
void dfs2(int u){
    color2[u]=k;
    sz++;
    lst=u;
    for(int vv:vt2[u]){
        int v=color[vv];
        if(!color2[v]){
            arr[u][v]=1;
            arr[v][u]=1;
            dfs2(v);
        }
    }
}
int construct(vector<vector<int>> pp) {
    p=pp;
	n=p.size();
	for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(p[i][j]==1){
                vt[i+1].pb(j+1);
                vt[j+1].pb(i+1);
            }
            else if(p[i][j]==2){
                vt2[i+1].pb(j+1);
                vt2[j+1].pb(i+1);
            }
            else if(p[i][j]==3){
                //cout<<"X1"<<endl;
                return 0;
            }
        }
	}
	for(int i=1;i<=n;i++){
        if(!color[i]){
            k=i;
            sz=0;
            dfs(i);
        }
	}
	for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(color[i]==color[j]&&p[i-1][j-1]!=1){
                //cout<<i<<' '<<j<<endl;
                //cout<<"X2"<<endl;
                return 0;
            }
        }
	}
	vector<pii>v;
	for(int id=1;id<=n;id++){
        int i=color[id];
        if(color2[i]) continue;
        k=i;
        sz=0;
        dfs2(i);
        if(lst==i){
            color2[i]=0;
        }
        else{
            arr[i][lst]=1;
            arr[lst][i]=1;
            v.pb({i,lst});
        }
	}
	for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(color2[i]>0&&color2[i]==color2[j]&&p[i-1][j-1]!=2){
                //cout<<"X3"<<endl;
                return 0;
            }
        }
	}
	for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(p[i-1][j-1]==0){
                int a=color[i];
                int b=color[j];
                arr[a][b]=1;
                arr[b][a]=1;
            }
        }
	}
	vector<vector<int>>ans;
	for(int i=1;i<=n;i++){
        vector<int>vt;
        for(int j=1;j<=n;j++){
            vt.pb(arr[i][j]);
        }
        ans.pb(vt);
	}
	build(ans);
	return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/

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