//#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;
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
