Submission #578051

#	Time	Username	Problem	Language	Result	Execution time	Memory
578051		perchuts	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	322 ms	69052 KiB

supertrees

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "supertrees.h"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

set<int>tree[1001];
bool vis[1001];
int pai[1001];

// void build(vector<vector<int>>b){
//     vector<ii>edges;
//     int n = sz(b[0]);
//     for(int i=0;i<n;++i){
//         for(int j=i+1;j<n;++j){
//             if(b[i][j])edges.pb({i,j});
//         }
//     }
//     for(auto [x,y]:edges)cout<<x<<" "<<y<<endl;
// }

int construct(vector<vector<int>>v){
    int n = sz(v[0]);
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            if(v[i][j]>2)return 0;//impossivel se v[i][j] == 3
            if(v[i][j]==1)tree[i].insert(j);//mesma arvore
        }
        assert(tree[i].count(i));//enunciado nao deixou isso claro
    }

    vector<vector<int>>ans(n,vector<int>(n));
    for(int i=0;i<n;++i){
        if(!vis[i]){
            vis[i] = 1, pai[i] = i;
            for(auto x:tree[i]){
                if(x==i)continue;
                vis[x] = 1, pai[x] = i, ans[i][x] = ans[x][i] = 1;
                if(tree[x]!=tree[i])return 0;
            }
        }
    }

    //as arvores estao todas certas!

    for(int i=0;i<n;++i)vis[i] = 0;

    for(int i=0;i<n;++i){
        if(vis[pai[i]])continue;
        int x = pai[i];
        vis[x] = 1;
        set<int>ciclo={x};
        for(int j=0;j<n;++j)if(v[x][pai[j]]==2)ciclo.insert(pai[j]);
        int ultimo = *ciclo.rbegin();
        if(sz(ciclo)==1)continue;//nao tem ciclo
        if(sz(ciclo)==2)return 0;//nao existe ciclo de tamanho 2
        for(auto y:ciclo){
            ans[ultimo][y] = ans[y][ultimo] = 1, vis[y] = 1, ultimo = y;
            for(int j=0;j<n;++j){
                if(pai[j]==y)continue;
                if(ciclo.count(pai[j])==0){
                    if(v[y][j]!=0)return 0;
                }else{
                    if(v[y][j]!=2)return 0;
                }
            }
        }
    }

    build(ans);

    return 1;
}

// int main(){
//     int n;cin>>n;
//     vector<vector<int>>v(n,vector<int>(n));
//     for(int i=0;i<n;++i)for(int j=0;j<n;++j)cin>>v[i][j];
//     cout<<construct(v)<<endl;
// }

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