Submission #430290

#	Time	Username	Problem	Language	Result	Execution time	Memory
430290		TryMax	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	276 ms	24132 KiB

supertrees

#include "supertrees.h"
#ifdef LOCAL
    #include "grader.cpp"
#endif // LOCAL
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int N = 1e5 + 10;

int was[N], was1[N], sz[N], pr[N];

int find_pr(int u){
    if(pr[u] == u)
        return u;
    return pr[u] = find_pr(pr[u]);
}

void union_sets(int a, int b){
    a = find_pr(a);
    b = find_pr(b);
    if(a == b)
        return;
    if(sz[a] > sz[b])
        swap(a, b);
    pr[a] = b;
    sz[b] += sz[a];
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> ans;
	ans.resize(n);
    bool f = true;
	for(int i = 0; i < n; ++i){
        ans[i].resize(n), sz[i] = 1, pr[i] = i;
        f &= (p[i][i] == 1);
	}
    vector<int> top;
    for(int i = 0; i < n; ++i){
        if(was[i])
            continue;
        top.pb(i);
        was[i] = 1;
        for(int j = 0; j < n; ++j)
            if(p[i][j] == 1 && was[j] == 0)
                was[j] = 1, ans[i][j] = 1, union_sets(i, j);
    }
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            if(find_pr(i) == find_pr(j)){
                f &= (p[i][j] == 1);
                p[i][j] = 2;
            }
//    for(int i = 0; i < n; ++i)
//        cout << find_pr(i) << " ";
//    cout << endl;
    for(int i = 0; i < top.size(); ++i){
        if(was1[top[i]])
            continue;
        vector<int> now;
        now.pb(top[i]);
        was1[top[i]] = 1;
        for(int j = 0; j < top.size(); ++j)
            if(was1[top[j]] == 0 && p[top[i]][top[j]] == 2 && find_pr(top[i]) != find_pr(top[j]))
                now.pb(top[j]), was1[top[j]] = 1, union_sets(top[i], top[j]);
        for(int j = 0; j < now.size() - 1; ++j)
            ans[now[j]][now[j + 1]] = 1;
        if(now.size() == 2)
            f = false;
        if(now.size() > 1)
            ans[now.back()][now[0]] = 1;
    }

//    for(int i = 0; i < n; ++i)
//        cout << find_pr(i) << " ";
//    cout << endl;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            if(find_pr(i) == find_pr(j)){
                f &= (p[i][j] == 2);
                p[i][j] = 0;
            }
//    for(int i = 0; i < n; ++i){
//        for(int j = 0; j < n; ++j)
//            cout << p[i][j] << " ";
//        cout << endl;
//    }
//    cout << f << endl;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j){
            f &= (p[i][j] == 0);
            ans[i][j] = ans[j][i] = (ans[i][j] | ans[j][i]);
        }
    if(f){
        build(ans);
        return 1;
    }else
        return 0;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1

1
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0

2
1 0
0 1

1
0 0
0 0

2
1 3
3 1

0
*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0; i < top.size(); ++i){
      |                    ~~^~~~~~~~~~~~
supertrees.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j = 0; j < top.size(); ++j)
      |                        ~~^~~~~~~~~~~~
supertrees.cpp:69:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int j = 0; j < now.size() - 1; ++j)
      |                        ~~^~~~~~~~~~~~~~~~

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