제출 #768218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
768218		Khizri	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	173 ms	34120 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 v:vt[u]){
        if(!color[v]&&!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){
                vt[i+1].pb(j+1);
                vt[j+1].pb(i+1);
            }
            else if(p[i][j]==3){
                return 0;
            }
        }
	}
	for(int i=1;i<=n;i++){
        if(!color[i]){
            k=i;
            sz=0;
            dfs(i);
            if(sz==1){
                color[i]=0;
            }
        }
	}
	for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(color[i]>0&&color[i]==color[j]&&p[i-1][j-1]!=1){
                return 0;
            }
        }
	}
	vector<pii>v;
	for(int i=1;i<=n;i++){
        if(color[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){
                return 0;
            }
        }
	}
	for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(p[i-1][j-1]==2&&!(color2[i]&&color2[j])){
                if(color2[i]){
                    int a=color2[i],b=color[j];
                    arr[a][b]=1;
                    arr[b][a]=1;
                }
                else{
                    int a=color[i],b=color2[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;
}

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