Submission #705857

#	Time	Username	Problem	Language	Result	Execution time	Memory
705857		Alihan_8	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	214 ms	24012 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));
    vector <int> par(n);
    iota(all(par), 0);
    auto F = [&](auto &&F, int x) -> int{
        return x == par[x] ? x : par[x] = F(F, par[x]);
    };
    auto find = [&](int x){
        return F(F, x);
    };
    auto merge = [&](int x, int y){
        x = find(x), y = find(y);
        if ( x == y ) return false;
        par[y] = x; return true;
    };
    for ( int i = 0; i < n; i++ ){
        for ( int j = 0; j < n; j++ ){
            if ( i == j ) continue;
            if ( !p[i][j] ){
                if ( find(i) == find(j) ){
                    return false;
                }
                continue;
            }
            if ( merge(i, j) ){
                ans[i][j] = ans[j][i] = true;
            }
        }
    }
    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: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4