#include "supertrees.h"
#include <cassert>
#include <map>
#include <vector>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define pll pair<ll, ll>
struct DSU{
vector<int> p;
int n, cnt;
DSU(int N){
n=N;
cnt=n;
p.resize(n, -1);
}
int get(int x){
return p[x]==-1?x:p[x]=get(p[x]);
}
bool unite(int a, int b){
a=get(a);
b=get(b);
if (a==b) return 0;
cnt--;
if (a<b) swap(a, b);
p[a]=b;
return 1;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = (int)p.size();
DSU tr(n), tr2(n);
vector<vector<int>> A(n);
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (i!=j and p[i][j]){
tr.unite(i, j);
if (p[i][j]==1) tr2.unite(i, j);
}
}
}
map<int, vector<int>> ccs;
for (int i=0; i<n; i++){
// assert(tr.get(i)<tr.cnt);
ccs[tr.get(i)].push_back(i);
}
vector<vector<int>> ans(n, vector<int>(n));
for (auto &[_, arr]:ccs){
map<int, vector<int>> groups;
for (auto ch:arr){
groups[tr2.get(ch)].push_back(ch);
}
vector<int> circle;
for (auto &[icc,mem]:groups){
for (ll j=1; j<(int)mem.size(); j++){
ans[mem[j]][mem[j-1]]=ans[mem[j-1]][mem[j]]=1;
}
circle.push_back(mem[0]);
}
if (circle.size()==1) continue;
for (ll j=0; j<(int)circle.size(); j++){
int nxt = (j+1)%(int)(circle.size());
ans[circle[j]][circle[nxt]]=ans[circle[nxt]][circle[j]]=1;
}
}
build(ans);
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
4 ms |
1244 KB |
Output is correct |
7 |
Correct |
105 ms |
22028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
4 ms |
1244 KB |
Output is correct |
7 |
Correct |
105 ms |
22028 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
4 ms |
1116 KB |
Output is correct |
13 |
Correct |
109 ms |
22100 KB |
Output is correct |
14 |
Incorrect |
0 ms |
344 KB |
Answer gives possible 1 while actual possible 0 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Incorrect |
0 ms |
348 KB |
Answer gives possible 1 while actual possible 0 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
35 ms |
5720 KB |
Output is correct |
5 |
Correct |
116 ms |
24148 KB |
Output is correct |
6 |
Correct |
114 ms |
24188 KB |
Output is correct |
7 |
Correct |
139 ms |
23968 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
28 ms |
6368 KB |
Output is correct |
10 |
Correct |
143 ms |
24148 KB |
Output is correct |
11 |
Correct |
118 ms |
24144 KB |
Output is correct |
12 |
Correct |
118 ms |
24044 KB |
Output is correct |
13 |
Correct |
0 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
29 ms |
6236 KB |
Output is correct |
17 |
Correct |
114 ms |
23932 KB |
Output is correct |
18 |
Correct |
115 ms |
24148 KB |
Output is correct |
19 |
Correct |
119 ms |
24044 KB |
Output is correct |
20 |
Correct |
114 ms |
24144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
4 ms |
1244 KB |
Output is correct |
7 |
Correct |
105 ms |
22028 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
4 ms |
1116 KB |
Output is correct |
13 |
Correct |
109 ms |
22100 KB |
Output is correct |
14 |
Incorrect |
0 ms |
344 KB |
Answer gives possible 1 while actual possible 0 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
4 ms |
1244 KB |
Output is correct |
7 |
Correct |
105 ms |
22028 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
4 ms |
1116 KB |
Output is correct |
13 |
Correct |
109 ms |
22100 KB |
Output is correct |
14 |
Incorrect |
0 ms |
344 KB |
Answer gives possible 1 while actual possible 0 |
15 |
Halted |
0 ms |
0 KB |
- |