oj.uz

답안 #300391

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
300391 2020-09-17T06:34:48 Z Dovran 슈퍼트리 잇기 (IOI20_supertrees) C++14
0 / 100
 1 ms 512 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;
/*
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Too few ways to get from 0 to 1, should be 2 found 0
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 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 #6
0 / 4.0

# 결과 실행 시간 메모리 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 -