제출 #431950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431950		A_D	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	284 ms	30656 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int NN=1e3+100;
bool vis[NN];
vector<int> g[NN][3];
vector<vector<int>> ans;
int s,e;
void dfs2(int u)
{
    vis[u]=1;
    for(auto x:g[u][1]){
        if(vis[x])continue;
        ans[u][x]=1;
        ans[x][u]=1;
        dfs2(x);
    }
}
void dfs(int u)
{
    e=u;
    vis[u]=1;
    for(auto x:g[u][2]){
        if(vis[x])continue;
        ans[u][x]=1;
        ans[x][u]=1;
        dfs(x);
    }
}
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++){
            if(p[i][j]==3){
                return 0;
            }
            if(i==j){
                if(p[i][j]!=1){
                    return 0;
                }
                continue;
            }
            g[i][p[i][j]].push_back(j);
            g[j][p[i][j]].push_back(i);
        }
    }
    for(int i=0;i<n;i++){
        if(vis[i]==0)dfs2(i);
    }
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++){
        s=i;
        e=i;
        ans[s][e]=1;
        if(vis[i]==0)dfs(i);
        ans[i][i]=0;
    }
    build(ans);
    return 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