Submission #315862

#	Time	Username	Problem	Language	Result	Execution time	Memory
315862		juggernaut	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	274 ms	26236 KiB

supertrees

#include"supertrees.h"
#include<bits/stdc++.h>
#ifdef EVAL
#else
#include"grader.cpp"
#endif
using namespace std;
int par[1005],pr[1005],n;
bool vis[1005];
vector<int>st[1005],comp;
vector<vector<int>>P,v;
int fin(int v){
    return v==par[v]?v:par[v]=fin(par[v]);
}
void unite(int x,int y){
    x=fin(x);
    y=fin(y);
    if(x!=y){
        if(st[x].size()<st[y].size())swap(x,y);
        st[x].insert(st[x].end(),st[y].begin(),st[y].end());
        st[y].clear();
        par[y]=x;
    }
}
void dfs(int vv){
    comp.push_back(vv);
    vis[vv]=1;
    pr[vv]=1;
    for(int i=0;i<n;i++)if(!vis[i]&&P[vv][i]==1)vis[i]=1,pr[i]=vv,v[vv][i]=v[i][vv]=1;
    for(int i=0;i<n;i++)if(!vis[i]&&P[vv][i]==2)dfs(i);
}
int construct(vector<vector<int>>p){
    P=p;
	n=p.size();
	int i,j;
	v.resize(n);
	fill(v.begin(),v.end(),vector<int>(n,0));
	for(i=0;i<n;i++)par[i]=i,st[i].push_back(i);
	for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(p[i][j]==3)return 0;
            if(p[i][j])unite(i,j);
        }
	}
	for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if((!p[i][j]&&fin(i)==fin(j))||(p[i][j]&&fin(i)!=fin(j)))return 0;
    for(i=0;i<n;i++)
    if(!st[i].empty()){
        comp.clear();
        dfs(st[i][0]);
        for(int j=1;j<comp.size();j++)v[comp[j]][comp[j-1]]=v[comp[j-1]][comp[j]]=1;
        if(comp.size()!=1)v[comp[0]][comp.back()]=v[comp.back()][comp[0]]=1;
        if(comp.size()==2)return 0;
        for(int vv:st[i])
            for(int to:st[vv])if(pr[vv]==pr[to]&&P[vv][to]!=1)return 0;
    }
	build(v);
	return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1

*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int j=1;j<comp.size();j++)v[comp[j]][comp[j-1]]=v[comp[j-1]][comp[j]]=1;
      |                     ~^~~~~~~~~~~~

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