Submission #794928

#	Time	Username	Problem	Language	Result	Execution time	Memory
794928		boyliguanhan	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	171 ms	28028 KiB

supertrees

#include "supertrees.h" 
#include <bits/stdc++.h>
using namespace std;
 
int comp[1010], tree[1010], comps, sz[1010], roots[1010][1010];
int construct(std::vector<std::vector<int>> p) {
    for(auto i:p)
        for(auto j: i)
            if(j>2)
                return 0;
    int n = p.size();
	std::vector<std::vector<int>> answer(n,vector<int>(n,0));
    for(int i = 0; i < n; i++) {
        bool determined=0;
        bitset<1024>notree;
        bitset<1024>notcomp;
        for(int j = 0; j < i; j++) {
            if(determined) {
                if(!p[i][j]){
                    if(comp[i]==comp[j]) 
                        return 0;
               } else if(comp[i]!=comp[j])
                    return 0;
                else if(p[i][j]==1&&tree[i]!=tree[j])
                    return 0;
            } else {
                if(!p[i][j])
                    notcomp[comp[j]]=1;
                else if(p[i][j]-1) {
                    if(notcomp[comp[j]]) return 0;
                    notcomp.reset();
                    notcomp.flip();
                    notcomp[comp[j]] = 0;
                    notree[tree[j]] = 1;
                    comp[i] = comp[j];
                } else {
                    if(notcomp[comp[j]]) return 0;
                    if(notree[tree[j]]) return 0;
                    answer[i][j] = answer[j][i] = 1;
                    tree[i] = tree[j];
                    comp[i] = comp[j];
                    notcomp.reset();
                    notcomp.flip();
                    notcomp[comp[j]] = 0;
                    notree.reset();
                    notree.flip();
                    notree[tree[j]] = 0;
                    determined = 1;
                }
            }
        }
        if(!comp[i]) {
            comp[i] = ++comps;
            roots[comp[i]][1] = i;
            sz[comps] = tree[i] = 1;
        } else if(!tree[i]) {
            tree[i] = ++sz[comp[i]];
            roots[comp[i]][sz[comp[i]]] = i;
        }
        if(notcomp[comp[i]]||notree[tree[i]]) return 0;
    } 
    for(int i = 1; i <= comps; i++) {
        if(sz[i]==1) continue;
        if(sz[i]==2) return 0;
        for(int j = 1; j < sz[i]; j++) {
            answer[roots[i][j]][roots[i][j+1]] = answer[roots[i][j+1]][roots[i][j]] = 1;
        }
        answer[roots[i][1]][roots[i][sz[i]]] = answer[roots[i][sz[i]]][roots[i][1]] = 1;
    }
	build(answer);
	return 1;
}

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