# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
301415 | 2020-09-17T22:56:03 Z | cuom1999 | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 261 ms | 30200 KB |
#include <bits/stdc++.h> #include "supertrees.h" using namespace std; struct Solver { int n; vector<bool> vs; vector<int> lineIndex; vector<vector<int>> p, line, cycle; Solver(vector<vector<int>> p): p(p), n(p.size()) { vs.resize(n); lineIndex.resize(n); line.resize(n); cycle.resize(n); } void dfs1(int a, int c) { if (vs[a]) return; vs[a] = 1; lineIndex[a] = c; line[c].push_back(a); for (int i = 0; i < n; i++) { if (p[a][i] == 1) dfs1(i, c); } } void dfs2(int a, int c) { if (vs[a]) return; vs[a] = 1; cycle[c].push_back(a); for (int i = 0; i < n; i++) { if (p[a][i] == 2) dfs2(i, c); } } int solve() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (p[i][j] == 3) return 0; } } for (int i = 0; i < n; i++) { if (!vs[i]) dfs1(i, i); } for (int i = 0; i < n; i++) { if (lineIndex[i] == i) vs[i] = 0; } for (int i = 0; i < n; i++) { if (!vs[i]) dfs2(i, i); } // construct res vector<vector<int>> res(n, vector<int>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j + 1 < line[i].size(); j++) { int x = line[i][j], y = line[i][j + 1]; res[x][y] = res[y][x] = 1; } if (cycle[i].size() > 1) cycle[i].push_back(cycle[i][0]); for (int j = 0; j + 1 < cycle[i].size(); j++) { int x = cycle[i][j], y = cycle[i][j + 1]; res[x][y] = res[y][x] = 1; } } build(res); // for (int i = 0; i < n; i++) { // cout << lineIndex[i] << " "; // } // cout << endl; // for (int i = 0; i < n; i++) { // if (cycle[i].size()) { // for (auto j: cycle[i]) cout << j << " "; // cout << endl; // } // } return 1; } }; int construct(vector<vector<int>> p) { return Solver(p).solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 0 ms | 256 KB | Output is correct |
6 | Correct | 11 ms | 1536 KB | Output is correct |
7 | Correct | 259 ms | 30076 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 0 ms | 256 KB | Output is correct |
6 | Correct | 11 ms | 1536 KB | Output is correct |
7 | Correct | 259 ms | 30076 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 0 ms | 256 KB | Output is correct |
10 | Correct | 0 ms | 256 KB | Output is correct |
11 | Correct | 0 ms | 256 KB | Output is correct |
12 | Correct | 11 ms | 1536 KB | Output is correct |
13 | Correct | 244 ms | 30200 KB | Output is correct |
14 | Incorrect | 0 ms | 256 KB | Answer gives possible 1 while actual possible 0 |
15 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Incorrect | 1 ms | 384 KB | Answer gives possible 1 while actual possible 0 |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 1 ms | 256 KB | Output is correct |
4 | Correct | 61 ms | 7800 KB | Output is correct |
5 | Correct | 248 ms | 30072 KB | Output is correct |
6 | Correct | 251 ms | 30200 KB | Output is correct |
7 | Correct | 259 ms | 30072 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 62 ms | 7800 KB | Output is correct |
10 | Correct | 251 ms | 30072 KB | Output is correct |
11 | Correct | 249 ms | 30200 KB | Output is correct |
12 | Correct | 261 ms | 30200 KB | Output is correct |
13 | Correct | 1 ms | 256 KB | Output is correct |
14 | Correct | 0 ms | 256 KB | Output is correct |
15 | Correct | 1 ms | 256 KB | Output is correct |
16 | Correct | 63 ms | 7928 KB | Output is correct |
17 | Correct | 251 ms | 30072 KB | Output is correct |
18 | Correct | 253 ms | 30072 KB | Output is correct |
19 | Correct | 245 ms | 30044 KB | Output is correct |
20 | Correct | 246 ms | 30072 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 0 ms | 256 KB | Output is correct |
6 | Correct | 11 ms | 1536 KB | Output is correct |
7 | Correct | 259 ms | 30076 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 0 ms | 256 KB | Output is correct |
10 | Correct | 0 ms | 256 KB | Output is correct |
11 | Correct | 0 ms | 256 KB | Output is correct |
12 | Correct | 11 ms | 1536 KB | Output is correct |
13 | Correct | 244 ms | 30200 KB | Output is correct |
14 | Incorrect | 0 ms | 256 KB | Answer gives possible 1 while actual possible 0 |
15 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 0 ms | 256 KB | Output is correct |
6 | Correct | 11 ms | 1536 KB | Output is correct |
7 | Correct | 259 ms | 30076 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 0 ms | 256 KB | Output is correct |
10 | Correct | 0 ms | 256 KB | Output is correct |
11 | Correct | 0 ms | 256 KB | Output is correct |
12 | Correct | 11 ms | 1536 KB | Output is correct |
13 | Correct | 244 ms | 30200 KB | Output is correct |
14 | Incorrect | 0 ms | 256 KB | Answer gives possible 1 while actual possible 0 |
15 | Halted | 0 ms | 0 KB | - |