Submission #338094

#	Time	Username	Problem	Language	Result	Execution time	Memory
338094		sealnot123	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	255 ms	22124 KiB

supertrees

/*
	Author: AquaBlaze
    Keqing best girl :)
    Nephren will always be in my heart
*/
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())
#define pc(x) putchar(x)
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long i64;
typedef tuple<int,int,int> iii;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#include "supertrees.h"

//#include "grader.cpp"

queue<int> bfs;

int construct(vvi p) {
	int n = p.size();
    
    // fundamental check
    int visit[n] = {};
    vi group;
    FOR(i, 0, n-1){
        if(!visit[i]){
            bfs.push(i);
            group.pb(i);
            visit[i] = 1;
            while(!bfs.empty()){
                int u = bfs.front();
                bfs.pop();
                FOR(j, 0, n-1){
                    if(p[u][j] && !visit[j]){
                        visit[j] = 1;
                        bfs.push(j);
                    }
                }
            }
            int x = SZ(group);
            FOR(j, 0, x-1){
                FOR(k, j+1, x-1){
                    if(!p[j][k]) return 0;
                }
            }
            group.clear();
        }
    }
    vvi answer(n, vi(n));
    int mx = 1;
    FOR(i, 0, n-1) FOR(j, 0, n-1) mx = max(mx, p[i][j]);
    if(mx == 1){
        int mark[n] = {};
        FOR(i, 0, n-1){
            if(mark[i]) continue;
            mark[i] = 1;
            FOR(j, 0, n-1){
                if(i == j) continue;
                if(p[i][j] && mark[j]) return 0;
                if(p[i][j]) answer[i][j] = answer[j][i] = 1, mark[j] = 1;
            }
        }
        build(answer);
        return 1;
    }
	build(answer);
	return 1;
}

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