Submission #315865

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

supertrees

#include"supertrees.h"
#include<bits/stdc++.h>
#ifdef EVAL
#else
#include"grader.cpp"
#endif
using namespace std;
vector<vector<int>>P,res;
vector<int>comp;
int N,timer,pr[1005],id[1005];
bool vis[1005];
void dfs(int v){
    comp.push_back(v);
    pr[v]=v;
    vis[v]=1;
    id[v]=timer;
    for(int i=0;i<N;i++)if(!vis[i]&&P[v][i]==1)vis[i]=1,pr[i]=v,id[i]=timer,res[v][i]=res[i][v]=1;
    for(int i=0;i<N;i++)if(!vis[i]&&P[v][i]==2)dfs(i);
}
int construct(vector<vector<int>>p){
    P=p;
    N=p.size();
    res.resize(N);
    fill(res.begin(),res.end(),vector<int>(N,0));
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)if(p[i][j]==3)return 0;
    for(int i=0;i<N;i++)
        if(!vis[i]){
            timer++;
            dfs(i);
            if(comp.size()==2)return 0;
            else if(comp.size()>2){
                int j;
                for(j=1;j<comp.size();j++)res[comp[j]][comp[j-1]]=res[comp[j-1]][comp[j]]=1;
                res[comp[j-1]][comp[0]]=res[comp[0]][comp[j-1]]=1;
            }
            comp.clear();
        }
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)
        if(pr[i]==pr[j]&&p[i][j]!=1)return 0;
        else if(id[i]==id[j]&&pr[i]!=pr[j]&&p[i][j]!=2)return 0;
        else if(id[i]!=id[j]&&p[i][j])return 0;
    build(res);
    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:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                 for(j=1;j<comp.size();j++)res[comp[j]][comp[j-1]]=res[comp[j-1]][comp[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