Submission #315838

#	Time	Username	Problem	Language	Result	Execution time	Memory
315838		juggernaut	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	271 ms	22268 KiB

supertrees

#include"supertrees.h"
#include<bits/stdc++.h>
#ifdef EVAL
#else
#include"grader.cpp"
#endif
using namespace std;
int par[1005];
bool vis[1005];
vector<int>st[1005];
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;
    }
}
int construct(vector<vector<int>>p){
	int n=p.size(),i,j;
	for(i=0;i<n;i++)par[i]=i,st[i].push_back(i);
	vector<vector<int>>v(n,vector<int>(n,0));
	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))return 0;
    for(i=0;i<n;i++)
    if(!st[i].empty()){
        vector<int>comp;
        for(int vv:st[i]){
            if(!vis[vv]){
                vis[vv]=1;
                for(int to:st[vv]){
                    if(vv!=to&&p[vv][to]==1&&!vis[to]){
                        vis[to]=1;
                        v[vv][to]=1;
                        v[to][vv]=1;
                    }
                }
                comp.push_back(vv);
            }
        }
        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;
    }
	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:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         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