제출 #724060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
724060		Urvuk3	슈퍼트리 잇기 (IOI20_supertrees)	C++17	19 / 100	227 ms	24068 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back

void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}

template<typename T,typename V>
void PRINT(pair<T,V>& x){
    cerr<<"{";
    PRINT(x.fi);
    cerr<<",";
    PRINT(x.se);
    cerr<<"}";
}
template<typename T>
void PRINT(T &x){
    int id=0;
    cerr<<"{";
    for(auto _i:x){
        cerr<<(id++ ? "," : "");
        PRINT(_i);
    }
    cerr<<"}";
}
void _PRINT(){
    cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
    PRINT(h);
    if(sizeof...(t)) cerr<<", ";
    _PRINT(t...);
}

#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)

vector<vector<int>> comp;
vector<int> par;

void Connect(int i,int j){
    i=par[i]; j=par[j];
    if(i==j) return;
    if(sz(comp[i])<sz(comp[j])) swap(i,j);
    for(int x:comp[j]){
        comp[i].pb(x);
        par[x]=i;
    }
    comp[j].clear();
}

int construct(vector<vector<int>> p) {
	int N=sz(p);
	comp.resize(N); par.resize(N);
    for(int i=0;i<N;i++){
        comp[i].pb(i); par[i]=i;
    }
	for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(p[i][j]==3) return 0;
            if(p[i][j]) Connect(i,j);
        }
	}
	vector<vector<int>> answer(N,vector<int>(N,0));
	vector<bool> vis(N,false);
	for(vector<int> c:comp){
        //Debug(c);
        if(sz(c)==2 && p[c[0]][c[1]]) return 0;
        for(int i:c){
            for(int j:c){
                if(p[i][j]==0) return 0;
            }
        }
        vector<int> cycle,tmp;
        for(int u:c){
            if(!vis[u]){
                for(int v:c){
                    if(p[u][v]==1){
                        tmp.pb(v);
                        vis[v]=true;
                    }
                }
                cycle.pb(u);
                for(int i=1;i<sz(tmp);i++){
                    int u=tmp[i],v=tmp[i-1];
                    answer[u][v]=1;
                    answer[v][u]=1;
                }
                //Debug(tmp);
                tmp.clear();
            }
        }
        //Debug(cycle);
        if(sz(cycle)>1){
            for(int i=0;i<sz(cycle);i++){
                if(i==0){
                    int u=cycle[0],v=cycle.back();
                    answer[u][v]=1;
                    answer[v][u]=1;
                }
                else{
                    int u=cycle[i],v=cycle[i-1];
                    answer[u][v]=1;
                    answer[v][u]=1;
                }
            }
        }
	}
	build(answer);
	return 1;
}

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