Submission #316678

#	Time	Username	Problem	Language	Result	Execution time	Memory
316678		talant117408	Connecting Supertrees (IOI20_supertrees)	C++17	46 / 100	267 ms	38008 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 <int> vis(1000);

int construct(vector<vector<int>> p){
    int n;
    n = p.size();
	for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(p[i][j] == 3)
                return 0;
        
    int i, j;
    vector <pair <vector <int>, vector <int>>> ways(n);
    vector <vector <int>> b(n, vector <int> (n)), accessible(n, vector <int> (n));
    vector <vector <int>> graph(n, vector <int> (n));
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i][j]){
                accessible[i].pb(j);
                if(j == i) continue;
                if(p[i][j]&1) ways[i].first.pb(j);
                else ways[i].second.pb(j);
            }
        }
    }
    for(i = 0; i < n; i++){
        if(!vis[i]){
            vis[i] = 1;
            for(j = 0; j < n; j++){
                if(p[i][j] && !vis[j] && accessible[i] != accessible[j]){
                    return 0;
                }
                vis[j] = 1;
            }
        }
        if(sz(ways[i].second) == 1){
            return 0;
        }
    }
    
    for(i = 0; i < n; i++){
        vis[i] = 0;
    }
    
    for(i = 0; i < n; i++){
        if(!vis[i]){
            vector <int> used(n), used2(n);
            for(j = 0; j < n; j++){
                if(p[i][j]){
                    used[j]++;
                    vis[j] = 1;
                }
            }
            for(j = 0; j < n; j++){
                if(p[i][j] && !used2[j]){
                    int ind = j;
                    for(auto to : ways[j].first){
                        used2[to]++;
                        used[to]--;
                        graph[to][j] = graph[j][to] = 1;
                    }
                    if(!sz(ways[j].first)) continue;
                    used[ind]++;
                }
            }
            vector <int> cycle;
            for(j = 0; j < n; j++){
                if(used[j]){
                    cycle.pb(j);
                }
            }
            
            for(j = 0; j < sz(cycle); j++){
                graph[cycle[j]][cycle[(j+1)%sz(cycle)]] = graph[cycle[(j+1)%sz(cycle)]][cycle[j]] = 1;
            }
        }
    }
    for(i = 0; i < n; i++){
        graph[i][i] = 0;
    }
    
    build(graph);
    
    return 1;
}

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