Submission #321419

#	Time	Username	Problem	Language	Result	Execution time	Memory
321419		grt	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	512 KiB

supertrees

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;

#define ST first
#define ND second
#define PB push_back

const int nax = 1000 + 10;
int n;
vi Graph[nax];
bool visited[nax];
vector<vi>comp;
vector<vi>access;
vi cur;

void build(vector<vi>v);

void dfs(int x) {
    visited[x] = 1;
    cur.PB(x);
    for(int nbh : Graph[x]) {
        if(!visited[nbh]) dfs(nbh);
    }
}

int construct(vector<vi> p) {
    int cnt3 = 0;
    n = (int)p.size();
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(p[i - 1][j - 1] == 1) {
                Graph[i].PB(j);
            }
            if(p[i - 1][j - 1] == 3) cnt3++;
        }
    }
    if(cnt3 > 0) return 0;
    bool ok = 1;
    for(int i = 1; i <= n; ++i) {
        if(!visited[i]) {
            cur = {};
            dfs(i);
            comp.PB(cur);
            for(int x : cur) {
                for(int y : cur) {
                    if(p[x - 1][y - 1] != 1) ok = 0;
                }
            }
        }
    }
    if(!ok) return 0;
    for(auto c : comp) {
        cur = {};
        int id = 0;
        for(auto c2 : comp) {
            if(c2 == c) {
                cur.PB(id);
                id++;
                continue;
            }
            int cnt0 = 0, cnt1 = 0, cnt2 = 0;
            for(int x : c) {
                for(int y : c2) {
                    if(p[x - 1][y - 1] == 0) cnt0++;
                    else if(p[x - 1][y - 1] == 1) cnt1++;
                    else if(p[x - 1][y - 1] == 2) cnt2++;
                }
            }
            assert(cnt1 == 0);
            if(cnt0 > 0 && cnt2 > 0) ok = 0;
            if(cnt2 > 0) {
                cur.PB(id);
            }
            id++;
        }
        access.PB(cur);
    }
    if(!ok) return 0;
    for(int i = 0; i <= n; ++i) visited[i] = 0;
    for(int i = 0; i < (int)comp.size(); ++i) {
        if(!visited[i]) {
            cur = access[i];
            visited[i] = 1;
            for(int x : cur) {
                visited[x] = 1;
                if(cur != access[x]) ok = 0;
            }
        }
    }
    if(!ok) return 0;
    vector<vi>g(n);
    for(int i = 0; i < n; ++i) g[i].resize(n);
    for(int nr = 0; nr < (int)access.size(); ++nr) {
        for(int x : comp[nr]) {
            for(int y : comp[nr]) {
                if(x != y) {
                    g[x - 1][y - 1] = 1;
                }
            }
        }
        //cout << nr << " ";
        for(int x : access[nr]) {
            if(x != nr) g[comp[nr][0] - 1][comp[x][0] - 1] = 1;
        }
    }
    build(g);
    //for(int i = 0; i < n; ++i) {
    //    for(int j = 0; j < n; ++j) {
    //        cout << g[i][j] << " ";
    //    }
    //    cout << "\n";
    //}
    return 1;
}

//int main() {
    //cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});
    //cout << construct({{1,3},{3,1}});
//}

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