#include <bits/stdc++.h>
using namespace std;
#ifndef ARTHUR_LOCAL
#include "supertrees.h"
#endif
#define len(x) int((x).size())
#ifdef ARTHUR_LOCAL
void build(vector<vector<int>> V)
{
for(auto row:V)
{
for(auto thing:row) cout << thing << " ";
cout << endl;
}
}
#endif
vector<int> comp;
vector<int> adj[1001];
bool vis[1001];
void dfs(int v)
{
vis[v]=1;
comp.push_back(v);
for(auto u:adj[v])
{
if(vis[u]) continue;
dfs(u);
}
}
int construct(vector<vector<int>> P) {
int n = (int)P.size();
vector<vector<int>> answer;
for (int i = 0; i < n; i++)
{
vector<int> row(n);
answer.push_back(row);
}
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(P[i][j] == 1)
{
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
vector<int> heads;
vector<vector<int>> headcomps;
for(int i=0; i<n; i++)
{
if(vis[i]) continue;
comp.clear();
dfs(i);
int m = (int)comp.size();
heads.push_back(i);
headcomps.push_back(comp);
for(int i=0; i<m; i++)
{
for(int j=i+1; j<m; j++)
{
if(P[comp[i]][comp[j]] != 1) return 0;
}
}
for(int i=1; i<m; i++)
{
answer[comp[0]][comp[i]]=1;
answer[comp[i]][comp[0]]=1;
// answer[comp[i]][comp[(i+1)%m]]=1;
// answer[comp[(i+1)%m]][comp[i]]=1;
}
}
vector<bool> headvis(n+1);
for(int i=0; i<len(heads); i++)
{
if(headvis[i]) continue;
headvis[i]=1;
vector<int> cur = {heads[i]};
for(int j=i+1; j<len(heads); j++)
{
if(P[heads[i]][heads[j]] == 2)
{
cur.push_back(heads[j]);
headvis[j]=1;
}
}
if(len(cur)==1) continue;
for(int j=0; j<len(cur); j++)
{
answer[cur[j]][cur[(j+1)%len(heads)]]=1;
answer[cur[(j+1)%len(heads)]][cur[j]]=1;
}
}
build(answer);
return 1;
}
#ifdef ARTHUR_LOCAL
int main()
{
construct({{1,2,0},{2,1,0},{0,0,1}});
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
1440 KB |
Output is correct |
7 |
Correct |
251 ms |
26232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
1440 KB |
Output is correct |
7 |
Correct |
251 ms |
26232 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
1280 KB |
Output is correct |
13 |
Correct |
244 ms |
22264 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
896 KB |
Output is correct |
17 |
Correct |
119 ms |
15000 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
60 ms |
5880 KB |
Output is correct |
21 |
Correct |
255 ms |
22648 KB |
Output is correct |
22 |
Correct |
239 ms |
22256 KB |
Output is correct |
23 |
Correct |
249 ms |
24184 KB |
Output is correct |
24 |
Correct |
244 ms |
22264 KB |
Output is correct |
25 |
Correct |
105 ms |
12792 KB |
Output is correct |
26 |
Correct |
101 ms |
12152 KB |
Output is correct |
27 |
Correct |
255 ms |
25208 KB |
Output is correct |
28 |
Correct |
239 ms |
22136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
288 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Incorrect |
1 ms |
384 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 |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
288 KB |
Output is correct |
4 |
Correct |
62 ms |
5880 KB |
Output is correct |
5 |
Correct |
251 ms |
22728 KB |
Output is correct |
6 |
Correct |
241 ms |
22136 KB |
Output is correct |
7 |
Correct |
309 ms |
24184 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Incorrect |
62 ms |
5880 KB |
Too many ways to get from 0 to 457, should be 0 found no less than 1 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
1440 KB |
Output is correct |
7 |
Correct |
251 ms |
26232 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
1280 KB |
Output is correct |
13 |
Correct |
244 ms |
22264 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
896 KB |
Output is correct |
17 |
Correct |
119 ms |
15000 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
60 ms |
5880 KB |
Output is correct |
21 |
Correct |
255 ms |
22648 KB |
Output is correct |
22 |
Correct |
239 ms |
22256 KB |
Output is correct |
23 |
Correct |
249 ms |
24184 KB |
Output is correct |
24 |
Correct |
244 ms |
22264 KB |
Output is correct |
25 |
Correct |
105 ms |
12792 KB |
Output is correct |
26 |
Correct |
101 ms |
12152 KB |
Output is correct |
27 |
Correct |
255 ms |
25208 KB |
Output is correct |
28 |
Correct |
239 ms |
22136 KB |
Output is correct |
29 |
Correct |
1 ms |
288 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Incorrect |
1 ms |
384 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
1440 KB |
Output is correct |
7 |
Correct |
251 ms |
26232 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
1280 KB |
Output is correct |
13 |
Correct |
244 ms |
22264 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
896 KB |
Output is correct |
17 |
Correct |
119 ms |
15000 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
60 ms |
5880 KB |
Output is correct |
21 |
Correct |
255 ms |
22648 KB |
Output is correct |
22 |
Correct |
239 ms |
22256 KB |
Output is correct |
23 |
Correct |
249 ms |
24184 KB |
Output is correct |
24 |
Correct |
244 ms |
22264 KB |
Output is correct |
25 |
Correct |
105 ms |
12792 KB |
Output is correct |
26 |
Correct |
101 ms |
12152 KB |
Output is correct |
27 |
Correct |
255 ms |
25208 KB |
Output is correct |
28 |
Correct |
239 ms |
22136 KB |
Output is correct |
29 |
Correct |
1 ms |
288 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Incorrect |
1 ms |
384 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |