Submission #316691

#	Time	Username	Problem	Language	Result	Execution time	Memory
316691		talant117408	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	259 ms	26360 KiB

supertrees

#include "supertrees.h"
#ifdef EVAL
#else 
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

vector <vector <int>> P, ans;
int N, compnum, par[1003], vis[1003], comp[1003];
vector <int> cycle;

void dfs(int u){
    cycle.pb(u);
    vis[u] = 1;
    par[u] = u;
    comp[u] = compnum;
    
    for(int i = 0; i < N; i++){
        if(!vis[i]){
            if(P[u][i] == 1){
                vis[i] = 1;
                par[i] = u;
                comp[i] = compnum;
                ans[i][u] = ans[u][i] = 1;
            }
        } 
    }
    for(int i = 0; i < N; i++){
        if(!vis[i]){
            if(P[u][i] == 2){
                dfs(i);
            }
        } 
    }
}

int construct(vector<vector<int>> p){
    P = p;
    N = sz(p);
    ans.resize(N, vector <int> (N));
    
    for(int i = 0; i < N; i++){
        if(!vis[i]){
            dfs(i);
            if(sz(cycle) == 2) return 0;
            else if(sz(cycle) > 2){
                for(int j = 0; j < sz(cycle); j++){
                    ans[cycle[j]][cycle[(j+1)%sz(cycle)]] = ans[cycle[(j+1)%sz(cycle)]][cycle[j]] = 1;
                }
            }
            ++compnum;
            cycle.clear();
        }
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(par[i] == par[j] && p[i][j] != 1) return 0;
            if(comp[i] == comp[j] && par[i] != par[j] && p[i][j] != 2) return 0;
            if(comp[i] != comp[j] && p[i][j]) return 0;
        }
    }
    
    build(ans);
    return 1;
}

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