Submission #334111

#	Time	Username	Problem	Language	Result	Execution time	Memory
334111		balbit	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	297 ms	28284 KiB

supertrees

#include <bits/stdc++.h>
#ifndef BALBIT
#include "supertrees.h"
#endif // BALBIT
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x.size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define bug(...)
#define endl '\n'
#endif // BALBIT

#define REP(i,n) for (int i = 0; i<n;++i)
#define REP1(i,n) for (int i = 1; i<=n;++i)

const int maxn = 1005;


int n;
vector<vector<int> > g;
vector<vector<int> > ans;
int c1[maxn], c2[maxn];
vector<int> vec1[maxn];
int colorhead[maxn];
bool seen[maxn];

void dfs1(int v, int c) {
    seen[v] = 1; c1[v] = c; vec1[c].pb(v);
    REP(u,n) {
        if (!seen[u] && g[v][u] == 1) {
            dfs1(u,c);
        }
    }
}

set<int> poscol;

void dfs2(int v, int c) {
    seen[v] = 1;
    poscol.insert(c1[v]);
    c2[v] = c;
    REP(u,n) {
        if (!seen[u] && (g[v][u] == 2 || g[v][u] == 1)) {
            dfs2(u,c);
        }
    }
}

inline void mark(int a, int b) {
    ans[a][b] = ans[b][a] = 1;
}

#ifdef BALBIT
void build(vector<vector<int> > x) {
    REP(i,n) REP(j,n) {
        if (x[i][j]) bug(i,j);
//        cout<<x[i][j]<<" \n"[j==n-1];
    }
}
#endif // BALBIT

int construct(vector<vector<int>> _p) {
    g = _p;
	n = g.size();
	ans = vector<vector<int> > (n, vector<int> (n,0));
    REP(i,n) REP(j,n) {
        if (g[i][j] == 3) {
            return 0;
        }
    }
    int NC = 0;
    REP(i,n) {
        if (!seen[i]) {
            colorhead[NC] = i;
            dfs1(i,NC++);
        }
    }
    // check if they are cliques
    REP(i,n) REP(j,n) {
        if (i != j && c1[i] == c1[j]) {
            if (g[i][j] != 1) return 0;
        }
    }
    REP(i,NC) {
        REP(j, SZ(vec1[i])) {
            if (j) mark(vec1[i][j], vec1[i][j-1]);
        }
    }
    memset(seen, 0, sizeof seen);
    int NC2 = 0;
    REP(i,n) {
        if (!seen[i]) {
            dfs2(i, NC2);
            vector<int> tmp;
            for (int x : poscol) {
                tmp.pb(x);
            }
            poscol.clear();
            if (SZ(tmp) == 2) {
                return 0;
            }
            if (SZ(tmp) > 1)
                REP(i, SZ(tmp)) {
                    int j = i == SZ(tmp)-1? 0 : i+1;
                    mark(colorhead[tmp[i]],colorhead[tmp[j]]);
                }
            ++NC2;
        }
    }

    REP(i,n) REP(j,n) {
        if (i != j && c2[i] == c2[j]) {
            if (g[i][j] != 1 && g[i][j] != 2) return 0;
        }
    }

    build(ans);
	return 1;
}

#ifdef BALBIT
signed main(){
//    bug(1,2);
    construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});
}
#endif

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