oj.uz

Submission #300649

# Submission time Handle Problem Language Result Execution time Memory
300649 2020-09-17T10:59:58 Z Dovran Connecting Supertrees (IOI20_supertrees) C++14
0 / 100
 1 ms 384 KB 
#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;
int vl[N];
/*
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]==2)
				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);
	for(int i=0; i<n; i++)
		vl[i]=-1;
	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;
	if(asd)
		return 0;
	
	for(int i=0; i<n; i++){
		if(sz[ata(i)]>1){
			if(vl[p[i]]>=0)
				c[vl[p[i]]][i]=c[i][vl[p[i]]]=1;
			vl[p[i]]=i;
		}
	}
	for(int i=0; i<n; i++)
		if(vl[p[i]]>=0)
			c[vl[p[i]]][i]=c[i][vl[p[i]]]=1, vl[p[i]]=-1;
			
	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 384 KB Output is correct
2 Incorrect 1 ms 384 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 384 KB Output is correct
2 Incorrect 1 ms 384 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 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 4.0

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