Submission #300391

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
300391	2020-09-17T06:34:48 Z	Dovran	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	512 KB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

#define N 1009
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define sz() size()
#define pb push_back
#define pp() pop_back()

using namespace std;

int n, sz[N], p[N];
vector<vector<int>>c;
int vis[N][N];
vector<pii>a;
vector<pii>b;
/*
void build(vector<vector<int>>m){
	for(int i=0; i<m.sz(); i++){
		for(int j=0; j<m[i].sz(); j++)
			cout<<m[i][j]<<' ';
		cout<<'\n';
	}
}
*/
int ata(int x){
	if(p[x]==x)
		return x;
	return p[x]=ata(p[x]);
}

void dsu(int x, int y){
	x=ata(x);
	y=ata(y);
	
	if(sz[y]>sz[x])
		swap(x, y);
	
	sz[x]+=sz[y];
	p[y]=x, sz[y]=0;
	
	return;
}

int construct(vector<vector<int>>v){
	n=v.sz();
	c.resize(n);
	for(int i=0; i<n; i++)
		sz[i]=1, p[i]=i;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			c[i].pb(0);
			if(v[i][j]==1 and i!=j)
				a.pb({i, j}), v[j][i]=3;
			if(v[i][j]==0)
				b.pb({i, j});
		}
	}
	for(auto i:a){
		if(ata(i.ff)!=ata(i.ss))
			dsu(i.ff, i.ss);
		
	}
	int asd=0;
	for(auto i:b)
		if(ata(i.ff)==ata(i.ss))
			asd=1, c[i.ff][i.ss]=c[i.ss][i.ff]=1;
	if(asd)
		return 0;
	
	build(c);
	return 1;
}
/*
int main(){
	int dsa, qwe;
	vector<vector<int>>v;
	cin>>dsa;
	v.resize(dsa);
	for(int i=0; i<dsa ;i++)
		for(int j=0; j<dsa; j++)
			cin>>qwe, v[i].pb(qwe);
	construct(v);
}
*/

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Incorrect	1 ms	256 KB	Too few ways to get from 0 to 1, should be 1 found 0
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Incorrect	1 ms	256 KB	Too few ways to get from 0 to 1, should be 1 found 0
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	416 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Incorrect	1 ms	384 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 ms	0 KB	-