Submission #705872

#	Time	Username	Problem	Language	Result	Execution time	Memory
705872		Alihan_8	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	236 ms	24208 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define int long long
// don't forget to call "build" and return (true or false)
int construct(vector <vector<int>> p){
    int n = (int)p.size();
    vector <vector<int>> ans(n, vector <int> (n));
    struct DSU{
        vector <int> par;
        void modify(int n){
            par.resize(n);
            iota(all(par), 0);
        }
        int find(int x){
            return x == par[x] ? x : par[x] = find(par[x]);
        }
        bool merge(int x, int y){
            x = find(x), y = find(y);
            if ( x == y ) return false;
            par[y] = x; return true;
        }
        bool same(int x, int y){
            return find(x) == find(y);
        };
    } L, R;
    L.modify(n), R.modify(n);
    // L - with one edge
    for ( int i = 0; i < n; i++ ){
        for ( int j = 0; j < n; j++ ){
            if ( i == j ) continue;
            if ( p[i][j] == 3 ) return false;
            if ( p[i][j] ) R.merge(i, j);
            if ( p[i][j] == 1 ) L.merge(i, j);
        }
    }
    for ( int i = 0; i < n; i++ ){
        for ( int j = 0; j < n; j++ ){
            if ( i == j ) continue;
            if ( !p[i][j] ){
                if ( R.same(i, j) ) return false;
                continue;
            }
            auto flag = p[i][j] != 1;
            if ( flag and L.same(i, j) ) return false;
        }
    }
    vector <int> used(n), roots[n];
    for ( int i = 0; i < n; i++ ){
        if ( used[i] ) continue;
        used[i] = true;
        roots[R.find(i)].pb(i);
        for ( int j = 0; j < n; j++ ){
            if ( i != j and L.same(i, j) ){
                ans[i][j] = ans[j][i] = true;
                used[j] = true;
            }
        }
    }
    for ( auto it: roots ){
        int sz = (int)it.size();
        if ( sz == 2 ) return false;
        for ( int i = 0; i < sz; i++ ){
            ans[it[i]][it[(i+1)%sz]] = true;
        }
    }
    for ( int i = 0; i < n; i++ ){
        for ( int j = 0; j < n; j++ ){
            if ( ans[i][j] ) ans[j][i] = true;
        }
        ans[i][i] = false;
    }
    build(ans);
    return true;
}
#if false
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    vector <vector<int>> p(n, vector <int> (n));
    for ( auto &i: p ){
        for ( auto &j: i ) cin >> j;
    }
    construct(p);

    cout << '\n';
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/
}
#endif

Compilation message (stderr)

supertrees.cpp: In function 'void IO(std::string)':
supertrees.cpp:12:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:12:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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