Submission #437493

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
437493	2021-06-26T11:33:25 Z	beep_boop	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	2 ms	332 KB

supertrees

/*
 * Created at 4:30 PM on 26 Jun, 2021
 */

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <iostream>
#include <cmath>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <numeric>
#include <cassert>

using namespace std;

#define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
#define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SZ(x) (int)(x).size()
#define vt vector
#define error(x) cout << #x << " = " << (x) << '\n'
#define trav(a, x) for(auto& (a): (x))
#define UNIQUE(x) (x).resize(distance((x).begin(),unique(ALL(x))))
#define DO if(true)

//typedef long long ll;
//typedef vector<ll> vi;
//typedef pair<ll,ll> pi;
#define mp make_pair
#define pb push_back
#define eb emplace_back

//#define int ll

typedef vector<int> vi;
typedef pair<int, int> pi;

//INF value
#ifndef int
#define INF int(2e9) + 15
#else
#define INF int(1e18) + 15
#endif

//All four are primes
#define mod 1000000007
#define hash_mod 23333333377
#define MT 1004006003999
#define hash_mod2 911382323

void setIO(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    if (name.length()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

template<typename T>
void read(vector<T> &a) {
    for (auto &x: a) cin >> x;
}

template<typename T>
void read(vector<T> &a, int n) {
    a.resize(n);
    for (auto &x: a) cin >> x;
}

template<class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &v) {
    out << "(";
    out << v.first << "," << v.second;
    return out << ")";
}

template<class T>
ostream &operator<<(ostream &out, const vector<T> &v) {
    out << "[";
    list(i, SZ(v)) {
        if (i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

template<typename T>
void print(vector<T> &a) {
    for (const auto &x: a) cout << x << ' ';
    cout << '\n';
}

void MOD(int &x, int m = mod) {
    x %= m;
    if (x < 0) x += m;
}

void MOD(int64_t &x, int m = mod) {
    x %= m;
    if (x < 0) x += m;
}

#define trace(...) dbg(#__VA_ARGS__, __VA_ARGS__)

template<typename T>
void dbg(const char *name, T &&arg1) {
    cout << name << " : " << arg1 << '\n';
}

template<typename T, typename... U>
void dbg(const char *names, T &&arg1, U &&... args) {
    const char *comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | ";
    dbg(comma + 1, args...);
}

template<class T>
void read(T &x) {
    cin >> x;
}

template<class T, class... U>
void read(T &t, U &... u) {
    read(t);
    read(u...);
}

int gcd(int a, int b) { return !a ? b : gcd(b % a, a); }

void build(vt<vi> b);
//void build(vt<vi> b){cout << b << '\n';}

struct DSU {
    int size = 1;
    vi link, sz;

    explicit DSU(int n){
        size = n;
        link.resize(n);
        iota(ALL(link), 0);
        sz.assign(n, 1);
    }

    int find(int x){
        while (x != link[x]){
            x = link[x];
        }
        return x;
    }

    int same(int x, int y){
        return find(x) == find(y);
    }

    void unite(int x, int y){
        x = find(x), y = find(y);

        if(x == y){
            return;
        }

        if(sz[x] < sz[y]){
            swap(x, y);
        }

        sz[x] += sz[y];
        link[y] = x;
    }
};

using ll = int64_t;

#define N 1010
int n;
vt<vi> p;

int construct(vt<vi> P){
    DO {
        p = P;
        n = SZ(p);
    }

    DSU dsu(n);

    list(i, n){
        rep(j, i + 1, n){
            if(p[i][j]){
                dsu.unite(i, j);
            }
        }
    }

    vt<vi> comp(n);
    list(i, n){
        comp[dsu.find(i)].eb(i);
    }

    vt<vi> ans(n, vi(n, 0));

    int x, y;
    list(i, n){
        if(SZ(comp[i]) == 1) continue;

        rep(j, 1, SZ(comp[i])){
            x = comp[i][j];
            y = comp[i][j - 1];

            ans[x][y] = 1;
            ans[y][x] = 1;
        }

        x = comp[i].front(), y = comp[i].back();
        ans[x][y] = 1;
        ans[y][x] = 1;
    }

    bool possible = true;
    list(i, n){
        if(SZ(comp[i]) == 1) continue;

        possible &= (SZ(comp[i]) > 2);
        list(j, SZ(comp[i])){
            rep(k, j + 1, SZ(comp[i])){
                possible &= (p[comp[i][j]][comp[i][k]] == 2);
            }
        }
    }

    if(!possible){
        return 0;
    }

    build(ans);
    return 1;
}

//int main(){
//    cout << construct(vt<vi>{vi{1, 0}, vi{0, 1}}) << '\n';
//}

Compilation message

supertrees.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<T>&)':
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
supertrees.cpp:90:5: note: in expansion of macro 'list'
   90 |     list(i, SZ(v)) {
      |     ^~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
supertrees.cpp:195:5: note: in expansion of macro 'list'
  195 |     list(i, n){
      |     ^~~~
supertrees.cpp:22:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
      |                               ^
supertrees.cpp:196:9: note: in expansion of macro 'rep'
  196 |         rep(j, i + 1, n){
      |         ^~~
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
supertrees.cpp:204:5: note: in expansion of macro 'list'
  204 |     list(i, n){
      |     ^~~~
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
supertrees.cpp:211:5: note: in expansion of macro 'list'
  211 |     list(i, n){
      |     ^~~~
supertrees.cpp:22:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
      |                               ^
supertrees.cpp:214:9: note: in expansion of macro 'rep'
  214 |         rep(j, 1, SZ(comp[i])){
      |         ^~~
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
supertrees.cpp:228:5: note: in expansion of macro 'list'
  228 |     list(i, n){
      |     ^~~~
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
supertrees.cpp:232:9: note: in expansion of macro 'list'
  232 |         list(j, SZ(comp[i])){
      |         ^~~~
supertrees.cpp:22:31: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
      |                               ^
supertrees.cpp:233:13: note: in expansion of macro 'rep'
  233 |             rep(k, j + 1, SZ(comp[i])){
      |             ^~~
supertrees.cpp: In function 'void setIO(const string&)':
supertrees.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Runtime error	2 ms	332 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Runtime error	2 ms	332 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Runtime error	1 ms	332 KB	Execution killed with signal 11
5	Halted	0 ms	0 KB	-