제출 #827068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827068		minhcool	슈퍼트리 잇기 (IOI20_supertrees)	C++17	96 / 100	187 ms	38180 KiB

supertrees

    //#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;
    		//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 : vc1[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() == 2) return 0;
    		//if(v2.size() > v.size()) return 0;
    		for(int j = 0; j < v2.size(); j++){
    			//cout << v2[j] << "\n";
    			//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;
    			}
    		}
    		if(v2.size() > 2) 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

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp:22:25: 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:126:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |       for(int j = 0; j < v2.size(); j++){
      |                      ~~^~~~~~~~~~~
supertrees.cpp:134:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |       if(v2.size() > 2) 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: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 0 / 4