제출 #800897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
800897		physics07	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	182 ms	26056 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int parent[1001];
int find(int x) {
    if(parent[x]<0) return x;
    return parent[x]=find(parent[x]);
}
void merge(int x, int y) {
    x=find(x), y=find(y);
    if(x==y) return;
    if(parent[x]>parent[y]) swap(x, y);
    parent[x]+=parent[y];
    parent[y]=x;
}
vector<int> adj[1001], cc[1001], root;
vector<vector<int>> ans;
bool visited[1001];
int construct(vector<vector<int>> p) {
	int n = p.size();
	ans.resize(n);
	for(int i=0; i<n; i++) {
        ans[i].resize(n);
        for(int j=0; j<n; j++) ans[i][j]=0;
	}
    for(int i=0; i<n; i++) {
        if(p[i][i]!=1) return 0;
        for(int j=0; j<n; j++) if(p[i][j]!=p[j][i] || p[i][j]==3) return 0;
    }
    memset(parent, -1, sizeof(parent));
    for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) if(p[i][j]) merge(i, j);
    for(int i=0; i<n; i++) root.push_back(find(i));
    sort(root.begin(), root.end());
    root.erase(unique(root.begin(), root.end()), root.end());
    vector<int> v;
    for(int i=0; i<(int)root.size(); i++) {
        for(int j=0; j<n; j++) if(find(j)==root[i]) cc[i].push_back(j);
        for(auto j: cc[i]) {
            for(auto k: cc[i]) if(j!=k) {
                if(!p[j][k]) return 0;
                if(p[j][k]==1) adj[j].push_back(k);
            }
            if(!visited[j]) {
                v.push_back(j);
                for(auto k: adj[j]) visited[k]=1;
            }
        }
        if(v.size()==2) return 0;
        for(auto j: v) for(auto k: v) if(j<k) {
            for(auto l: adj[j]) for(auto m: adj[k]) if(l==m || p[l][m]==1) return 0;
        }
        for(auto j: v) for(auto l: adj[j]) for(auto k: adj[j]) if(p[k][l]==2) return 0;
        for(auto j: v) for(auto k: adj[j]) ans[j][k]=ans[k][j]=1;
        if(v.size()>2) for(int j=0; j<(int)v.size(); j++) {
            int a=v[j], b=(j?v[j-1]:v.back());
            ans[a][b]=ans[b][a]=1;
        }
        v.clear();
        memset(visited, 0, sizeof(visited));
    }
    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