Submission #758911

#	Time	Username	Problem	Language	Result	Execution time	Memory
758911		1bin	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	194 ms	28008 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1005;
int par[NMAX], vis[NMAX], p[NMAX][NMAX], a, b;
vector<int> C[NMAX], V, t;
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}

void dfs(int x){
    if(vis[x]) return;
    vis[x] = 1;
    t.emplace_back(x);
    for(int& y : V) if(!vis[y] && p[x][y] == 2) dfs(y);
    return;
}

int construct(vector<vector<int>>p_){
    int n = p_.size(), a, b;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) p[i][j] = p_[i][j];
    vector<vector<int>> E(n, vector<int>(n, 0));
    
    memset(par, -1, sizeof(par));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++){
            if(p[i][j] == 3) return 0;
            a = find(i); b = find(j);
            if(a == b) continue;
            if(p[i][j] == 1){
                par[b] = a; E[i][j] = E[j][i] = 1;
            }
        }
    
    
    for(int i = 0; i < n; i++) C[find(i)].emplace_back(i);
    for(int i = 0; i < n; i++)
        if(find(i) == i){
            V.emplace_back(i);
            for(int&x : C[i])
                for(int j = 0; j < n; j++)
                    if(p[x][j] != p[i][j]) return 0;
        }

    
    for(int& x : V)
        if(!vis[x]){
            t.clear();
            dfs(x);
            int sz = t.size();
            if(sz == 1) continue;
            
            for(int i = 0; i < sz; i++){
                a = t[i], b = t[(i + 1) % sz];
                E[a][b] = E[b][a] = 1;
                for(int j = 0; j < sz; j++)
                    if(i != j && p[t[i]][t[j]] != 2) return 0;
            }
        }
    build(E);
    return 1;
}

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vector<vector<int>> v (n, vector<int>(n, 0));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) cin >> v[i][j];
    cout << construct(v) << '\n';
    return 0;
}
*/

/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1

2
1 0
0 1

2
1 3
3 1

*/

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