Submission #535414

#	Time	Username	Problem	Language	Result	Execution time	Memory
535414		mario05092929	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	198 ms	28072 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int n,p[1005],p2[1005],c[1005];
vector <vector <int>> v,A;
vector <int> g;

int Find(int x) {return (x^p[x] ? p[x] = Find(p[x]) : x);}
int Find2(int x) {return (x^p2[x] ? p2[x] = Find2(p2[x]) : x);}

void merge(int x,int y) {
    if(Find(x) == Find(y)) return;
    v[x][y] = v[y][x] = 1;
    p[p[y]] = p[x];
}

void merge2(int x,int y) {
    x = Find2(x), y = Find2(y);
    if(x == y) return;
    p2[y] = x;
}

void dfs(int x) {
    g.push_back(x);
    c[x] = 1;
    for(int i = 0;i < n;i++) {
        if(A[x][i] == 2&&Find(i) == i&&!c[i]) dfs(i);
    }
}

int construct(std::vector<std::vector<int>> B) {
    A = B;
    n = A.size();
	v.resize(n);
	for(int i = 0;i < n;i++) v[i].resize(n,0);
	for(int i = 0;i < n;i++) p[i] = p2[i] = i;
    for(int i = 0;i < n;i++) {
        for(int j = i+1;j < n;j++) {
            if(A[i][j] == 3) return 0;
            if(A[i][j] == 1) merge(i,j);
            if(A[i][j]) merge2(i,j);
        }
    }
    for(int i = 0;i < n;i++) {
        if(!c[i]&&Find(i) == i) {
            g.clear();
            dfs(i);
            if(g.size() == 1) continue;
            if(g.size() == 2) return 0;
            g.push_back(i);
            for(int j = 0;j < g.size()-1;j++) v[g[j]][g[j+1]] = v[g[j+1]][g[j]] = 1;
        }
    }
    for(int i = 0;i < n;i++) {
        for(int j = i+1;j < n;j++) {
            if(Find(i) == Find(j)) {
                if(A[i][j]^1) return 0;
            }
            else if(Find2(i) == Find2(j)) {
                if(A[i][j]^2) return 0;
            }
            else if(A[i][j]) return 0;
        }
    }
    build(v);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:51:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for(int j = 0;j < g.size()-1;j++) v[g[j]][g[j+1]] = v[g[j+1]][g[j]] = 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