Submission #625139

#	Time	Username	Problem	Language	Result	Execution time	Memory
625139		Dremix10	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	212 ms	29088 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<x<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define p2(x,y) {}
    #define pv(x) {}
#endif
const ll INF = 2e18+5;
const int MOD = 1e9+7;
const int N = 1005;

vector<vector<int> > ans;
int v[N];
vector<vector<vector<int> > > a(N,vector<vector<int> >(3,vector<int>()));

int nn;
bool flag = true;

vector<int> par(N),siz(N,1);
vector<vector<int> > g(N);
vector<int> s(N),e(N);

int find(int x){
    return (par[x] == x) ? x : par[x] = find(par[x]);
}
bool go = false;
bool join(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)return false;
    if(g[y].size() > g[x].size())swap(x,y);
    siz[x] += siz[y];
    par[y] = x;
    for(auto v : g[y])g[x].push_back(v);
    g[y].clear();
    p2(s[x],e[x])
    p2(s[y],e[y])
    if(go)
        ans[e[x]][s[y]] = ans[s[y]][e[x]] = 1;
    e[x] = e[y];
    return true;

}

int construct(std::vector<std::vector<int>> p) {
	int i,j,n = p.size();
    ans.assign(n,vector<int>(n,0)); 
    for(i=0;i<n;i++){
        g[i].push_back(i);
        for(j=0;j<n;j++){
            if(i==j)continue;
            if(p[i][j] == 3)return 0;
            a[i][p[i][j]].push_back(j);
        }
    }

    iota(all(par),0);
    iota(all(s),0);
    iota(all(e),0);
    
    for(i=0;i<n;i++){
        if(v[i]){
            continue;
        }
        //vector<int> chk;
        //chk.push_back(i);
        int x = i;
        v[i] = true;
        for(auto j : a[i][1]){
            join(i,j);
            p2(i,j)
            //chk.push_back(j);    
            ans[x][j] = ans[j][x] = 1;
            x = j;

            v[j] = true;
        }
        s[find(i)] = i;
        e[find(i)] = i;
        for(int k=0;k<n;k++){
            bool ok = true;
            int need = p[i][k];
            for(auto j : g[find(i)]){
                if(j == k)continue;
                if(p[j][k] != need){
                    ok = false;
                    break;
                }
            }
            if(!ok){
                flag = false;
                break;
            }
        }

    }
    if(!flag)return 0;
    fill(all(siz),1);
    go = true;
    for(i=0;i<n;i++){
        for(auto x : a[i][2]){
            //if(find(i) == find(x))continue;
            for(auto v1 : g[find(x)]){
                if(p[i][v1] != 2){
                    return 0;
                }
            }
            //ans[i][x] = ans[x][i] = 1;
            join(i,x);
            p2(i,x)
        }
    }

    for(i=0;i<n;i++){
        if(siz[find(i)] == 2)return 0;
    }

    for(i=0;i<n;i++){
        int x = s[find(i)];
        int y = e[find(i)];
        if(siz[find(i)] == 1)continue;
        ans[x][y] = ans[y][x] = 1;
    }

    if(!flag)return 0;
    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