Submission #827072

#	Time	Username	Problem	Language	Result	Execution time	Memory
827072		minhcool	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	195 ms	36596 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] == 3) return 0;
        			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

Compilation message (stderr)

supertrees.cpp:22:29: 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:127:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |           for(int j = 0; j < v2.size(); j++){
      |                          ~~^~~~~~~~~~~
supertrees.cpp:135:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |           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: 4 / 4