# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
366898 | 2021-02-15T16:33:55 Z | rumen_m | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 290 ms | 30316 KB |
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; const int maxn = 1005; vector <short> g[maxn]; vector <short> ones[maxn]; short id[maxn], ids = 0; bool vis[maxn]; vector <int> groups[maxn]; //short ans[maxn][maxn]; vector <vector <int> > ans; short newids[maxn]; void dfs(int v) { id[v]=ids; int i; for(i=0;i<g[v].size();i++) { if(id[g[v][i]]==0)dfs(g[v][i]); } } void solve(int v) { newids[v] = ids; vis[v] = 1; int i; for(i=0;i<ones[v].size();i++) { if(!vis[ones[v][i]]) { ans[v][ones[v][i]] = 1; solve(ones[v][i]); } } } int construct(std::vector<std::vector<int>> p) { int n = p.size(); ans.resize(n); int i,j,t; for(i=0;i<n;i++) ans[i].resize(n); for(i=0;i<n;i++) for(j=0;j<n;j++) { if(i==j)continue; if(p[i][j]==3)return 0; if(p[i][j]>0) { /* for(t=0;t<n;t++) { if((p[i][t]>0)^(p[j][t]>0)==1)return 0; if(p[i][j]==1) if(p[i][t]==1^p[j][t]==1)return 0; }*/ } if(p[i][j]!=0) { g[i].push_back(j); g[j].push_back(i); } if(p[i][j]==1) { ones[i].push_back(j); ones[j].push_back(i); } } for(i=0;i<n;i++) { if(id[i]==0){ids++;dfs(i);} } for(i=0;i<n;i++) { if(!vis[i]) { groups[id[i]].push_back(i); ids++; solve(i); } } for(i=1;i<=ids;i++) { if(groups[i].size()==2)return 0; if(groups[i].size()<=2)continue; ans[groups[i][0]][groups[i][groups[i].size()-1]] = 1; for(j=1;j<groups[i].size();j++) { ans[groups[i][j-1]][groups[i][j]] = 1; } } ///std::vector<std::vector<int>> answer; for (int i = 0; i < n; i++) { //std::vector<int> row; //row.resize(n); for(j=0;j<n;j++) { // row[j] = ans[i][j]|ans[j][i]; ans[i][j] = ans[i][j]|ans[j][i]; if(i==j)continue; if(p[i][j]==0&&id[i]==id[j]){return 0;} if(p[i][j]==1&&newids[i]!=newids[j])return 0; } //answer.push_back(row); } build(ans); return 1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 12 ms | 1772 KB | Output is correct |
7 | Correct | 290 ms | 30316 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 12 ms | 1772 KB | Output is correct |
7 | Correct | 290 ms | 30316 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 10 ms | 1260 KB | Output is correct |
13 | Runtime error | 120 ms | 24684 KB | Execution killed with signal 11 |
14 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 10 ms | 1260 KB | Output is correct |
9 | Runtime error | 125 ms | 24812 KB | Execution killed with signal 11 |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 64 ms | 5996 KB | Output is correct |
5 | Correct | 265 ms | 23276 KB | Output is correct |
6 | Correct | 248 ms | 22252 KB | Output is correct |
7 | Correct | 280 ms | 26220 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 62 ms | 5996 KB | Output is correct |
10 | Runtime error | 127 ms | 25708 KB | Execution killed with signal 11 |
11 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 12 ms | 1772 KB | Output is correct |
7 | Correct | 290 ms | 30316 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 10 ms | 1260 KB | Output is correct |
13 | Runtime error | 120 ms | 24684 KB | Execution killed with signal 11 |
14 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 12 ms | 1772 KB | Output is correct |
7 | Correct | 290 ms | 30316 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 10 ms | 1260 KB | Output is correct |
13 | Runtime error | 120 ms | 24684 KB | Execution killed with signal 11 |
14 | Halted | 0 ms | 0 KB | - |