Submission #370019

#	Time	Username	Problem	Language	Result	Execution time	Memory
370019		iliccmarko	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	384 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); }
#define mod 1000000007LL
const int N = 1050;
vector<int> g[N];
int n;
int s[N], parent[N];
int grupa[N];


int find_parent(int u)
{
    while(parent[u]!=u)
    {
        parent[u] = parent[parent[u]];
        u = parent[u];
    }
    return u;
}

void dsu(int u, int v)
{
    u = find_parent(u);
    v = find_parent(v);
    if(u!=v)
    {
        if(s[u]<s[v]) swap(u, v);
        s[u] += s[v];
        parent[v] = u;
    }
}


int construct(vector<vector<int> > p)
{
    n = len(p);
    for(int i = 0;i<n;i++) if(p[i][i]!=1) return 0;
    for(int i = 0;i<n;i++)
    {
        for(int j = i+1;j<n;j++)
        {
            if(p[i][j]==3)
            {
                grupa[i] = grupa[j] = 3;
                g[i].pb(j);
                g[j].pb(i);
            }
        }
    }
    for(int i = 0;i<n;i++)
    {
        if(grupa[i]) continue;
        for(int j = i+1;j<n;j++)
        {
            if(i==j) continue;
            if(grupa[j]) continue;
            if(p[i][j]==2)
            {
                grupa[i] = 2;
                grupa[j] = 2;
                g[i].pb(j);
                g[j].pb(i);
            }
        }
    }
    for(int i = 0;i<n;i++)
    {
        if(grupa[i]) continue;
        for(int j = i+1;j<n;j++)
        {
            if(i==j) continue;
            if(grupa[j]) continue;
            if(p[i][j]==1)
            {
                grupa[i] = grupa[j] = 1;
                g[i].pb(j);
                g[j].pb(i);
            }
        }
    }
    for(int i = 0;i<n;i++)
    {
        for(int x : g[i])
            dsu(i, x);
    }
    for(int i = 0;i<n;i++) parent[i] = find_parent(i);
    int moze = 1;
    for(int i = 0;i<n;++i)
    {
        int x = grupa[i];
        int cnt = 0;
        int raz = 0;
        for(int j = 0;j<n;j++)
        {
            if(i==j) continue;
            if(p[i][j]!=x&&x!=0) raz++;
            if(p[i][j]==x) cnt++;
        }
        if(raz) moze = 0;
        if(cnt!=s[parent[i]]&&x!=0) moze = 0;
    }
    if(!moze) return 0;
    std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	for(int i = 0;i<n;i++) for(int j = 0;j<n;j++) answer[i][j] = 0;
	for(int i = 0;i<n;i++) for(int x : g[i]) answer[i][x] = 1;
    build(answer);
    return 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