제출 #414550

#제출 시각아이디문제언어결과실행 시간메모리
414550InternetPerson10슈퍼트리 잇기 (IOI20_supertrees)C++14
100 / 100
251 ms24064 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; bool taken[1001]; int nums[1001], cycs[1001]; vector<vector<int>> paths; vector<vector<int>> cycles; vector<vector<int>> ans; int construct(std::vector<std::vector<int>> p) { vector<vector<int>>().swap(paths); vector<vector<int>>().swap(cycles); vector<vector<int>>().swap(ans); int n = p.size(); ans.resize(n); for(int i = 0; i < n; i++) { ans[i].resize(n); if(!taken[i]) { taken[i] = true; nums[i] = paths.size(); paths.push_back(vector<int>()); for(int j = i; j < n; j++) { if(p[i][j] == 1) { paths[nums[i]].push_back(j); taken[j] = true; nums[j] = nums[i]; } } } } // for(int i = 0; i < n; i++) cout << nums[i] << ' '; // cout << '\n'; for(int i = 0; i < n; i++) taken[i] = false; for(int i = 0; i < (int)paths.size(); i++) { if(!taken[i]) { taken[i] = true; cycles.push_back(vector<int>()); cycles[cycles.size() - 1].push_back(i); cycs[i] = cycles.size() - 1; for(int j = i+1; j < (int)paths.size(); j++) { if(p[paths[i][0]][paths[j][0]] == 2) { taken[j] = true; cycles[cycles.size() - 1].push_back(j); cycs[j] = cycles.size() - 1; } } } } // cout << "yehey\n"; // for(int i = 0; i < n; i++) cout << cycs[i] << ' '; // cout << '\n'; bool sad = false; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { int pi = nums[i], pj = nums[j]; int ci = cycs[pi], cj = cycs[pj]; if(p[i][j] == 0) { if(pi == pj || ci == cj) sad = true; } else if(p[i][j] == 1) { if(pi != pj) sad = true; } else if(p[i][j] == 2) { if(pi == pj || ci != cj) sad = true; } else { sad = true; } } } for(int i = 0; i < (int)cycles.size(); i++) { if(cycles[i].size() == 2) sad = true; } if(sad) { return 0; } // cout << "Yehey\n"; for(int i = 0; i < (int)paths.size(); i++) { for(int j = 1; j < (int)paths[i].size(); j++) { ans[paths[i][j]][paths[i][j-1]] = 1; ans[paths[i][j-1]][paths[i][j]] = 1; } } for(int i = 0; i < (int)cycles.size(); i++) { if(cycles[i].size() == 1) continue; ans[paths[cycles[i][0]][0]][paths[cycles[i][cycles[i].size() - 1]][0]] = 1; ans[paths[cycles[i][cycles[i].size() - 1]][0]][paths[cycles[i][0]][0]] = 1; for(int j = 1; j < (int)cycles[i].size(); j++) { ans[paths[cycles[i][j-1]][0]][paths[cycles[i][j]][0]] = 1; ans[paths[cycles[i][j]][0]][paths[cycles[i][j-1]][0]] = 1; } } 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...