Submission #1041367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041367		HD1	Connecting Supertrees (IOI20_supertrees)	C++14	46 / 100	111 ms	47032 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];
set<ll> s, c;
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;//x en 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]==1){
                 unir(i,j);
            }
            if(p[i][j]!=p[j][i])return 0;
        }
    }
    vector<vector<int>> gfo(n,vector<int>(n));
    for(int i=0; i<n; i++){
        fiend(f[i]);
        fiend(i);
        if(f[i]!=i)adj[f[i]].pb(i);// aqui estan cada subarbol de 1 o  mas
        s.insert(f[i]);//representante de cada grupo
    }

    for(auto u:s){//armamos subarboles en la lista dea dj
        for(auto v:adj[u]){
            gfo[v][u]=1;
            gfo[u][v]=1;
        }
    }
    // for(int i=0; i<n; i++){//armamos subarboles
    //     if(sz(adj[i])){
    //         for(int j=0; j+1<sz(adj[i]); j++){
    //             gfo[adj[i][j]][adj[i][j+1]]=1;
    //             gfo[adj[i][j+1]][adj[i][j]]=1;
    //         }
    //     }
    // }
    for(int i=0; i<n; i++){
        adj[i].clear();
        for(int j=0; j<n; j++){
            if(p[i][j]==2){
                 unir(f[i],f[j]);
            }
        }
    } 
    for(auto u:s){
        fiend(f[u]);
        fiend(u);
        if(f[u]!=u)adj[f[u]].pb(u);
        c.insert(f[u]);
    }
    //cout<<sz(c)<<'\n';
    for(auto x:c){
        //cout<<x<<' ';
        adj[x].pb(x);
        for(int i=0; i<sz(adj[x]); i++){
            int v=adj[x][i%sz(adj[x])];
            int u=adj[x][(i+1)%sz(adj[x])];
           if(v!=u){ 
                gfo[v][u]=1;
                gfo[u][v]=1;
            }
        }
    }
    //cout<<'\n';
    // for(auto it:s){//representante de cada grupo
    //     for(int i=0; i<n; i++){//par ver si tiene un 2
    //         if(it==f[i])continue;
    //         if(p[it][i]==2){
    //             gfo[it][f[i]]=1;
    //             gfo[f[i]][it]=1;
    //         }
    //     }
    // }
    build(gfo);
    return 1;
}
/* con fe
9
0 1 1 1 2 2 2 2 2
1 0 1 1 2 2 2 2 2
1 1 0 1 2 2 2 2 2
1 1 1 0 2 2 2 2 2
2 2 2 2 0 2 2 2 2 
2 2 2 2 2 0 2 1 2 
2 2 2 2 2 2 0 2 1
2 2 2 2 2 1 2 0 2
2 2 2 2 2 2 1 2 0
*/

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