Submission #685806

#	Time	Username	Problem	Language	Result	Execution time	Memory
685806		Sunbae	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	207 ms	31824 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
vector<int> parent, Size;
vector<pii> zero, two;
vector<int>nodes;
int findUpar(int node){
    if(node == parent[node]) return node;
    return parent[node] = findUpar(parent[node]);
}
void Union(int u, int v){
    int pu = findUpar(u), pv = findUpar(v);
    if(pu == pv) return ;
    if(Size[pu] > Size[pv]){
        parent[pv] = pu; Size[pu] += Size[pv];
    }else{
        parent[pu] = pv; Size[pv] += Size[pu];
     }
}
bool cycle(int sr, vector<int>Adj[], vector<bool>&visited, int n){
    visited[sr] = true;
    queue<pii>q; //{node, par}
    q.push({sr, -1});
    while(!q.empty()){
        int node = q.front().first;
        int par = q.front().second;
        q.pop();
        for(int adjNode: Adj[node]){
            if(!visited[adjNode]){
                visited[adjNode] = true;
                q.push({adjNode, node});
            }else if(par != adjNode){
                return true;
            }
        }
    }
    return false;
}
int construct(vector<vector<int>>p){
    int n = p.size(); parent.resize(n); Size.resize(n);
    for(int i = 0; i<n; i++) parent[i] = i, Size[i] = 1;
    vector<vector<int>>adj(n, vector<int>(n, 0));
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            if(p[i][j] == 0){
                 zero.push_back({i, j}); /// i and j must not be in the same compo
            }else if(p[i][j] == 1){
                Union(i, j);
            }else if(p[i][j] == 2){
                two.push_back({i, j});
            }else if(p[i][j] == 3){
                return 0;
            }
        }
    }
    ///mark 1
    for(int i = 0; i<n; i++){
        int pi = findUpar(i);
        if(pi != i){
            adj[i][pi] = 1; adj[pi][i] = 1;
        }
    }
    vector<int> Adj[n];
    ///mark 2
    for(pair<int,int> it: two){
        int u = it.first, v = it.second;
        int pu = findUpar(u), pv = findUpar(v);
        if(pu == pv) return 0;
        adj[pu][pv] = 1; adj[pv][pu] = 1;
        Adj[pu].push_back(pv);
        Adj[pv].push_back(pu);
    }
    ///2-> check cycle
  /*
    vector<bool>visited(n, false);
    int cnt = 0;
    for(int i = 0; i<n; i++){
        if(!visited[i]){
            bool Cycle = cycle(i, Adj, visited, n);
            if(Cycle) cnt++;
        }
    }
    if(cnt != 1){
        return 0;
    }*/
    ///Union 2
    for(pii it: two){
        Union(it.first, it.second);
    }
    ///Check zero
    for(pii it: zero){
        int u = it.first, v = it.second;
        int pu = findUpar(u), pv = findUpar(v);
        if(pu == pv) return 0;
    }
    build(adj);
    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