제출 #306311

#제출 시각아이디문제언어결과실행 시간메모리
306311miello슈퍼트리 잇기 (IOI20_supertrees)C++14
46 / 100
254 ms22392 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int MXN = 1005; vector<int> par_line(MXN, 0), par_comp(MXN, 0), line[MXN], cycle_vertex[MXN]; int root(int i, vector<int> &par) { while(i != par[par[i]]) { par[i] = par[par[i]]; i = par[par[i]]; } return i; } void mergeset(int a, int b, vector<int> &par) { par[root(a, par)] = root(b, par); } int construct(std::vector<std::vector<int>> p) { int n = p.size(); std::vector<std::vector<int>> answer; for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); answer.push_back(row); par_line[i] = i; par_comp[i] = i; } for(int i = 0; i < n; i++) { bool cycle_data = false, found_comp = false; for(int j = 0; j < n; j++) { if(i == j) continue; if(p[i][j] != 0) { if(p[i][j] == 3) { return 1; } found_comp = true; if(p[i][j] == 2) { cycle_data = true; if(root(i, par_comp) != root(j, par_comp)) { mergeset(i, j, par_comp); } continue; } if(root(i, par_line) != root(j, par_line)) { mergeset(i, j, par_line); } } } if(!cycle_data) { par_comp[i] = -1; } if(!found_comp) { par_line[i] = -1; } } for(int i = 0; i < n; i++) { if(par_line[i] != -1) { line[root(i, par_line)].push_back(i); } } for(int i = 0; i < n; i++) { int sz = line[i].size(); if(sz) { if(par_comp[line[i][0]] != -1){ cycle_vertex[root(line[i][0], par_comp)].push_back(line[i][0]); } } for(int j = 0; j < sz - 1; j++) { int x = line[i][j], y = line[i][j + 1]; answer[x][y] = answer[y][x] = 1; } } for(int i = 0; i < n; i++) { int sz = cycle_vertex[i].size(); if(sz >= 3) { cycle_vertex[i].push_back(cycle_vertex[i][0]); for(int j = 0; j < sz; j++) { int x = cycle_vertex[i][j], y = cycle_vertex[i][j + 1]; answer[x][y] = answer[y][x] = 1; } } else if(sz > 0) { return 1; } } build(answer); return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...