Submission #316685

#	Time	Username	Problem	Language	Result	Execution time	Memory
316685		talant117408	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1092 ms	39932 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), incycle(1000);
int nn;
vector <vector <int>> possible;
vector <vector <int>> graph, edges;

void dfs(int origin, int u, int p, int flag, int val){
    possible[origin][u] = val;
    vis[u] = 1;
    for(auto j : edges[u]){
        if(!vis[j]){
            if(incycle[u] && incycle[j] && !flag){
                int flag2 = 1, val2 = 2;
                dfs(origin, j, u, flag2, val2);
            }
            else{
                dfs(origin, j, u, flag, val);
            }
        }
    }
}

int construct(vector<vector<int>> p){
    int n;
    n = p.size();
    nn = n;
    graph.resize(n, vector <int> (n));
	possible.resize(n, vector <int> (n));
    edges.resize(n, vector <int> (n));
    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));
    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;
                        edges[to].pb(j);
                        edges[j].pb(to);
                    }
                    if(!sz(ways[j].first)) continue;
                    used[ind]++;
                }
            }
            vector <int> cycle;
            for(j = 0; j < n; j++){
                if(used[j]){
                    cycle.pb(j);
                    incycle[j] ++;
                }
            }
            
            for(j = 0; j < sz(cycle); j++){
                edges[cycle[j]].pb(cycle[(j+1)%sz(cycle)]);
                edges[cycle[(j+1)%sz(cycle)]].pb(cycle[i]);
                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] = vis[i] = 0;
    }
    
    for(i = 0; i < n; i++){
        dfs(i, i, -1, 0, 1);
        for(j = 0; j < n; j++){
            vis[j] = 0;
        }
    }
    if(p != possible) return 0;
    
    build(graph);
    
    return 1;
}

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