oj.uz

답안 #827048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
827048 2023-08-16T08:22:30 Z minhcool 슈퍼트리 잇기 (IOI20_supertrees) C++17
0 / 100
 9 ms 14432 KB 
//#define local
#ifndef local
#include "supertrees.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int sz1[N], rt1[N];

int sz2[N], rt2[N];

int root1(int x){
	return (x == rt1[x] ? x : rt1[x] = root1(rt1[x]));
}

void merge1(int x, int y){
	x = root1(x), y = root1(y);
	if(x == y) return;
	if(sz1[x] < sz1[y]) swap(x, y);
	sz1[x] += sz1[y];
	rt1[y] = x;
}

int root2(int x){
	return (x == rt2[x] ? x : rt2[x] = root2(rt2[x]));
}

void merge2(int x, int y){
	x = root2(x), y = root2(y);
	if(x == y) return;
	if(sz2[x] < sz2[y]) swap(x, y);
	sz2[x] += sz2[y];
	rt2[y] = x;
}

vector<int> vc1[N], vc2[N];

bool ok[N];

int construct(vector<vector<int>> p) {
	int n = p.size();
	for(int i = 0; i < n; i++){
		vc1[i].clear(), vc2[i].clear();
	}
	//int n = p.size();
	for(int i = 0; i < n; i++){
		rt1[i] = i, sz1[i] = 1;
		rt2[i] = i, sz2[i] = 1;
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			if(p[i][j] == 0){
				if(root1(i) == root1(j)) return 0;
			//	if(root2(i) == root2(j)) return 0;
			}
			if(p[i][j] >= 1){
			//	if(root2(i) == root2(j)) return 0;
				merge1(i, j);
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			if(p[i][j] == 0){
				if(root1(i) == root1(j)) return 0;
			//	if(root2(i) == root2(j)) return 0;
			}
		}
	}
	for(int i = 0; i < n; i++) vc1[root1(i)].pb(i);
	vector<vector<int>> answer;
	answer.resize(n);
	for(int i = 0; i < n; i++) answer[i].resize(n);
	for(int i = 0; i < n; i++){
		if(root1(i) != i) continue;
		vector<int> v;
		bool has2 = 0;
		for(auto it : vc1[i]){
			bool ck2 = 1;
			for(auto it2 : vc1[i]) has2 |= (p[it][it2] == 2);
		}
		//for(auto it : vc1[i]) ok[it] = 0;
		//for(auto it : v) ok[it] = 1;
		//if(v.size() <= 1 && has2) return 0;
		if(!has2) continue;
		for(auto it : vc1[i]){
			for(auto it2 : vc2[i]){
				if(ok[it] || ok[it2] || it == it2) continue;
				if(p[it][it2] == 1) merge2(it, it2);
			}
		}
		for(auto it : vc1[i]) if(!ok[it]) vc2[root2(it)].pb(it);
		vector<int> v2;
		for(auto it : vc1[i]){
			if(ok[it] || root2(it) != it) continue;
			v2.pb(it);
			for(auto it2 : vc2[it]){
				for(auto it3 : vc2[it]){
					if(it2 == it3) continue;
					if(p[it2][it3] == 2) return 0;
				}
			}
		}
		//if(v2.size() > v.size()) return 0;
		for(int j = 0; j < v2.size(); j++){
			//answer[v[j]][v2[j]] = 1;
			for(auto it : vc2[v2[j]]){
				if(it == v2[j]) continue;
				answer[it][v2[j]] = answer[v2[j]][it] = 1;
			}
		}
		for(int j = 0; j < v2.size(); j++) answer[v2[j]][v2[(j + 1) % v2.size()]] = answer[v2[(j + 1) % v2.size()]][v2[j]] = 1;
	}
	build(answer);
	return 1;
}

#ifdef local
void process(){
	int a, b;
	cin >> a >> b;
	cout << a + b << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) process();
}
#endif

Compilation message

supertrees.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:104:9: warning: unused variable 'ck2' [-Wunused-variable]
  104 |    bool ck2 = 1;
      |         ^~~
supertrees.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   for(int j = 0; j < v2.size(); j++){
      |                  ~~^~~~~~~~~~~
supertrees.cpp:137:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for(int j = 0; j < v2.size(); j++) answer[v2[j]][v2[(j + 1) % v2.size()]] = answer[v2[(j + 1) % v2.size()]][v2[j]] = 1;
      |                  ~~^~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14408 KB Output is correct
2 Incorrect 7 ms 14420 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 9 ms 14408 KB Output is correct
2 Incorrect 7 ms 14420 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 7 ms 14408 KB Output is correct
2 Correct 9 ms 14408 KB Output is correct
3 Correct 6 ms 14432 KB Output is correct
4 Incorrect 8 ms 14412 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14316 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Incorrect 7 ms 14404 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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14408 KB Output is correct
2 Incorrect 7 ms 14420 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 9 ms 14408 KB Output is correct
2 Incorrect 7 ms 14420 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -