제출 #309349

#제출 시각아이디문제언어결과실행 시간메모리
309349mihai145슈퍼트리 잇기 (IOI20_supertrees)C++14
46 / 100
268 ms34320 KiB
#include "supertrees.h" #include <vector> #include <iostream> const int NMAX = 1000; std::vector <std::pair <int, int> > edges; std::vector <std::vector <int>> input; int N; std::vector <std::pair <int, int>> g[NMAX + 1]; bool seen[NMAX + 1]; int nrComp; std::vector <int> comp[NMAX + 1]; void dfsComp(int node) { seen[node] = true; comp[nrComp].push_back(node); for(auto it : g[node]) if(!seen[it.first]) dfsComp(it.first); } int kId, chainId[NMAX + 1]; std::vector < int > currentChain; void dfs(int node, int par) { chainId[node] = kId; currentChain.push_back(node); if(par != -1) edges.push_back({par, node}); for(auto it : g[node]) if(chainId[it.first] == 0 && it.second == 1) dfs(it.first, node); } bool SolveComp(int c) { std::vector <int> representatives; for(auto node : comp[c]) if(chainId[node] == 0) { ++kId; currentChain.clear(); dfs(node, -1); representatives.push_back(currentChain[0]); } if((int)representatives.size() == 2) return 0; if((int)representatives.size() > 2) { for(int i = 1; i < (int)representatives.size(); i++) edges.push_back({representatives[i], representatives[i - 1]}); edges.push_back({representatives[0], representatives.back()}); } for(int i = 0; i < (int)comp[c].size(); i++) for(int j = 0; j < (int)comp[c].size(); j++) if(i != j) { if(chainId[i] != chainId[j]) { //if(input[i][j] != 2) //return false; } else { //if(input[i][j] != 1) //return false; } } return true; } int construct(std::vector<std::vector<int>> p) { input = p; N = p.size(); for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) if(i != j && p[i][j] > 0) { if(p[i][j] == 3) return 0; g[i].push_back({j, p[i][j]}); } for(int i = 0; i < N; i++) if(!seen[i]) { nrComp++; dfsComp(i); } bool haveSol = true; for(int i = 1; i <= nrComp; i++) { haveSol &= SolveComp(i); if(!haveSol) return 0; } std::vector<std::vector<int>> answer; for (int i = 0; i < N; i++) { std::vector<int> row; row.resize(N); answer.push_back(row); } for(auto it : edges) answer[it.first][it.second] = answer[it.second][it.first] = 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...