Submission #302777

#	Time	Username	Problem	Language	Result	Execution time	Memory
302777		mhy908	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	272 ms	30200 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

int n, arr[1010][1010], ans[1010][1010], tnum[1010];

struct UNION_FIND{
    int par[1010];
    UNION_FIND(){for(int i=1; i<=1000; i++)par[i]=i;}
    int findpar(int a){return a==par[a]?a:par[a]=findpar(par[a]);}
    void mergepar(int a, int b){par[findpar(a)]=findpar(b);}
}cyc, tree;

vector<int> rt[1010];

int construct(vector<vector<int> > p){
	n=p.size();
	for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)arr[i+1][j+1]=p[i][j];
	}
	for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(arr[i][j]==3)return 0;
        }
        if(arr[i][i]!=1)return 0;
	}
	for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(arr[i][j]==1&&i!=j)tree.mergepar(i, j);
        }
	}
	for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(tree.findpar(i)==tree.findpar(j)&&arr[i][j]!=1)return 0;
        }
	}
	for(int i=1; i<=n; i++)tnum[i]=tree.findpar(i);
	for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(arr[i][j]==2)cyc.mergepar(tnum[i], tnum[j]);
        }
	}
	for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(tnum[i]==tnum[j])continue;
            if(cyc.findpar(tnum[i])==cyc.findpar(tnum[j])&&arr[i][j]!=2)return 0;
        }
	}
	for(int i=1; i<=n; i++){
        rt[cyc.findpar(tnum[i])].eb(tnum[i]);
        if(i==tnum[i])continue;
        ans[i][tnum[i]]=1;
        ans[tnum[i]][i]=1;
	}
	for(int i=1; i<=n; i++){
        svec(rt[i]);
        press(rt[i]);
        if(rt[i].size()<=1)continue;
        for(int j=0; j<rt[i].size()-1; j++){
            ans[rt[i][j]][rt[i][j+1]]=1;
            ans[rt[i][j+1]][rt[i][j]]=1;
        }
        ans[rt[i][0]][rt[i].back()]=1;
        ans[rt[i].back()][rt[i][0]]=1;
	}
	vector<vector<int> > ret;
	for(int i=1; i<=n; i++){
		vector<int> vc;
		vc.resize(n);
		for(int j=1; j<=n; j++){
            if(ans[i][j])vc[j-1]=1;
		}
		ret.push_back(vc);
	}
	build(ret);
	return 1;
}

Compilation message (stderr)

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

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