Submission #1026351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026351		HD1	Connecting Supertrees (IOI20_supertrees)	C++14	19 / 100	137 ms	48868 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ll(x.size())
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAX=1e6;
int f[MAX];
vector<int> adj[MAX];
int fiend(int u){
    if(f[u] == u)return u;
    return f[u]=fiend(f[u]);
}
void unir(int u,int v){
    int x=fiend(u);
    int y=fiend(v);
    if(x!=y){
        f[x]=y;
    }
    return;
}
int construct(vector<vector<int>> p) {
    int n = p.size();
    for(int i=0; i<n; i++){
        f[i]=i;
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(p[i][j]){
                unir(i,j);
            }
        }
    }
    vector<vector<int>> gfo(n,vector<int>(n));
    for(int i=0; i<n; i++){
        fiend(f[i]);
        fiend(i);
        adj[f[i]].pb(i);
    }
    for(int i=0; i<n; i++){
        if(sz(adj[i])==0 || sz(adj[i])==1)continue;
        if(sz(adj[i])<3){
            return 0;
        }
        for(int j=0; j<sz(adj[i]); j++){
            gfo[adj[i][j]][adj[i][(j+1)%sz(adj[i])]]=1;
            gfo[adj[i][(j+1)%sz(adj[i])]][adj[i][j]]=1;
        }
        for(int j=0; j<sz(adj[i]); j++){
            for(int k=0; k<sz(adj[i]); k++){
                if(adj[i][k]!=adj[i][j] && (p[adj[i][k]][adj[i][j]]!=2 ||p[adj[i][j]][adj[i][k]]!=2))return 0;
            }
        }
    }
    build(gfo);
    return 1;
}
/* con fe
7
0 0 0 0 0 0 0
0 0 2 2 0 0 0 
0 2 0 2 0 0 0
0 2 2 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
*/

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