oj.uz

답안 #903249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
903249 2024-01-11T06:33:19 Z ByeWorld 슈퍼트리 잇기 (IOI20_supertrees) C++14
0 / 100
 1 ms 464 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
using namespace std;
const int MAXN = 1e3+10;
const double SMALL = 1e-6;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;

int n;
bool tag[MAXN], done[MAXN];
vector <vector<int>> adj;
vector <int> cc[MAXN];

void bd(int x, int y){
	adj[x][y] = 1; adj[y][x] = 1;
}

struct DSU {
	int par[MAXN], siz[MAXN];
	void bd(){
		for(int i=0; i<n; i++){
			par[i] = i; siz[i] = 1;
			cc[i].pb(i);
		}
	}
	int f(int x){
		if(x == par[x]) return x;
		return par[x] = f(par[x]);
	}
	bool con(int x, int y){
		return f(x) == f(y);
	}
	void mer(int x, int y){
		if(con(x, y)) return;
		x = f(x); y = f(y);
		if(siz[x] > siz[y]) swap(x, y);
		par[x] = y; siz[y] += siz[x];
		for(auto in : cc[x]) cc[y].pb(in);
	}
} A;

int construct(vector<vector<int>> p) {
	n = p.size();
	vector <int> te(n);
	for(int i=0; i<n; i++) adj.pb(te);
	A.bd();

	for(int i = 0; i < n; i++) {
		if(done[i]) continue;
		for(int x=0; x<n; x++) tag[x] = 0;

		vector <int> vec; vec.pb(i); tag[i] = 1;
		for(int j=i+1; j < n; j++){
			if(p[i][j] == 1){
				vec.pb(j); tag[j] = 1;
			}	
		}
		//for(auto in : vec) cout << in << "pp\n";
		for(auto in : vec){
			//cout << in << " in\n";
			done[in] = 1;
			for(int x=0; x<n; x++){
				if(tag[x] && p[in][x] != 1) return 0; //harusnya 1
				if(!tag[x] && p[in][x] == 1) return 0;
			}
		}
		for(int i=0; i+1<vec.size(); i++){ // build
			bd(vec[i], vec[i+1]);
			A.mer(vec[i], vec[i+1]);
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++) cout << adj[i][j] << ' ';
		cout << '\n';
	}

	for(int i=0; i<n; i++) done[i] = 0;
	for(int i = 0; i < n; i++) {
		if(done[i]) continue;
		for(int x=0; x<n; x++) tag[x] = 0;

		vector <int> vec; vec.pb(i); tag[i] = 1;
		for(int j=i+1; j < n; j++){
			if(p[i][j] == 2){
				vec.pb(j); tag[j] = 1;
			}	
		}
		for(auto x : vec){
			for(auto y : vec){
				if(x==y) continue; 
				if(A.con(x, y)) return 0;
			}
		}
		//for(auto in : vec) cout << in << "pp\n";
		for(auto in : vec){
			//cout << in << " in\n";
			done[in] = 1;
			for(int x=0; x<n; x++){
				if(x==in) continue;
				if(tag[x] && p[in][x] != 2) return 0; //harusnya 1
				if(!tag[x] && p[in][x] == 2) return 0;
			}
		}
		for(int i=0; i+1<vec.size(); i++){ // build
			bd(vec[i], vec[i+1]);
		}
		bd(vec[0], vec.back());
	}

	for(int i=0; i<n; i++) adj[i][i] = 0;
	build(adj);
	return 1;
}

Compilation message

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

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 464 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 352 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -