제출 #306332

#제출 시각아이디문제언어결과실행 시간메모리
306332andreiomd슈퍼트리 잇기 (IOI20_supertrees)C++14
40 / 100
272 ms31368 KiB
/// Subtasks 1, 2, 3; #include "supertrees.h" #include <vector> using namespace std; const int NMAX = 1e3 + 1; int N; int roads[NMAX][NMAX]; vector < int > tree[NMAX], cycle[NMAX]; bool Edge[NMAX][NMAX]; vector < int > List; bool Sel_tree[NMAX], Sel_cycle[NMAX]; int Id_tree[NMAX], Id_cycle[NMAX]; vector < int > line; vector < vector < int > > ans; bool OK = 1; static inline void Add_Edge (int X, int Y) { Edge[X][Y] = Edge[Y][X] = 1; return; } static inline void DFS_tree(int Node, int Id) { List.push_back(Node), Sel_tree[Node] = 1, Id_tree[Node] = Id; for(auto it : tree[Node]) if(!Sel_tree[it]) DFS_tree(it, Id); return; } static inline void Build_trees () { for(int i = 1; i <= N; ++i) if(!tree[i].empty() && !Sel_tree[i]) { List.clear(), DFS_tree(i, i); if((int)List.size() > 1) for(int j = 0; j < (int)List.size() - 1; ++j) Add_Edge(List[j], List[j + 1]); } return; } static inline void DFS_cycle (int Node, int Id) { List.push_back(Node), Sel_cycle[Node] = 1, Id_cycle[Node] = Id; for(auto it : cycle[Node]) if(!Sel_cycle[it]) DFS_cycle(it, Id); return; } static inline void Build_cycles () { for(int i = 1; i <= N; ++i) if(!cycle[i].empty() && !Sel_cycle[i]) { List.clear(), DFS_cycle(i, i); if((int)List.size() > 1) for(int j = 0; j < (int)List.size() - 1; ++j) Add_Edge(List[j], List[j + 1]); if((int)List.size() > 2) Add_Edge(i, List[(int)List.size() - 1]); else OK = 0; } return; } static inline void Solve () { Build_trees(); Build_cycles(); return; } static inline void Reconstruct () { for(int i = 1; i <= N; ++i) { line.clear(); for(int j = 1; j <= N; ++j) line.push_back(Edge[i][j]); ans.push_back(line); } return; } static inline bool Check () { for(int i = 1; i < N; ++i) for(int j = i + 1; j <= N; ++j) if(roads[i][j] == 0) { if(Id_tree[i] == Id_tree[j] && Id_tree[i]) return 0; if(Id_cycle[i] == Id_cycle[j] && Id_cycle[i]) return 0; } return (1 & OK); } int construct (vector < vector < int > > p) { N = (int)p.size(); for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) { roads[i + 1][j + 1] = p[i][j]; if(i == j) continue; if(p[i][j] == 1) tree[i + 1].push_back(j + 1); else if(p[i][j] == 2) cycle[i + 1].push_back(j + 1); else if(p[i][j] == 3) return 0; } Solve(); if(!Check()) return 0; Reconstruct(); build(ans); 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...