제출 #910139

#제출 시각아이디문제언어결과실행 시간메모리
910139nightfalSimurgh (IOI17_simurgh)C++14
51 / 100
91 ms6236 KiB
#include <cstdio> #include <iostream> #include <cassert> #include <vector> #include <cstdlib> #include <string> #include <utility> #include <tuple> using namespace std; std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v); int count_common_roads(const std::vector<int>& r); bool isSubtask1(int n) {return n<=7;} bool isSubtask2(int n) {return n<=50;} bool isSubtask3(int n) {return n<=240;} void dfs3(int startNode, int startEdge, int parent, int now, vector<vector<pair<int,int>>>& edgeL, vector<int>& r2, vector<int>& dNode, vector<vector<int>>& alterEdge) { dNode[now]=1; for(auto& elem: edgeL[now]) { int nextNode,nextEdge; tie(nextNode,nextEdge) = elem; if (nextNode==parent) continue; if (nextNode==startNode) {alterEdge[startEdge].push_back(nextEdge); continue;} if (!dNode[nextNode]) { r2.push_back(nextEdge); dfs3(startNode,startEdge,now,nextNode,edgeL,r2,dNode,alterEdge); } } return; } vector<int> subtask3(int n, std::vector<int>& u, std::vector<int>& v) { int m = u.size(); vector<int> r; vector<int> treeEdge(m); vector<bool> testedEdge(m); // Edge list vector<vector<pair<int,int>>> edgeL(n); for(int i=0; i<m; i++) { edgeL[u[i]].push_back(make_pair(v[i],i)); edgeL[v[i]].push_back(make_pair(u[i],i)); } // printf("Edge list\n"); // for(int i=0; i<n; i++) {printf("%d: ",i); for(auto& elem: edgeL[i]) printf("(%d,%d) ",elem.first,elem.second); printf("\n");} printf("\n"); for(int startNode=0; startNode<n; startNode++) { // printf("------ startNode = %d ------\n",startNode); vector<int> dNode(n); vector<vector<int>> alterEdge(m); dNode[startNode] = 1; vector<int> r2, r2StartEdgeIdx; int secondNode,startEdge; for(auto& elem: edgeL[startNode]) { tie(secondNode,startEdge) = elem; if (dNode[secondNode]) continue; r2.push_back(startEdge); r2StartEdgeIdx.push_back(r2.size()-1); dfs3(startNode,startEdge,startNode,secondNode,edgeL,r2,dNode,alterEdge); } // printf("r2: "); for(int elem: r2) printf("%d ",elem); printf("\n"); // printf("r2StartEdgeIdx: "); for(int elem: r2StartEdgeIdx) printf("%d ",elem); printf("\n"); // printf("alterEdge: \n"); // for(int i=0; i<n; i++) { printf("%d: ",i); for(auto& elem: alterEdge[i]) printf("%d ",elem); printf("\n");} // int defaultCount = count_common_roads(r2); // tested가 있는 경우에 그것을 가지고 untested의 treeEdge 여부 계산가능 for(int startEdgeIdx: r2StartEdgeIdx) { vector<int> result; int maxValue = -1; int startEdge = r2[startEdgeIdx], newStartEdge = r2[startEdgeIdx]; vector<int> cycle; cycle.push_back(startEdge); for(int anEdge: alterEdge[startEdge]) cycle.push_back(anEdge); // printf("cycle: "); for(int elem: cycle) printf("%d ",elem); printf("\n"); bool hasTestedEdge = false; for(int anEdge: cycle) if (testedEdge[anEdge]) {hasTestedEdge = true; newStartEdge = anEdge; break;} // printf("hasTestedEdge = %d, newStartEdge = %d\n",hasTestedEdge,newStartEdge); if (hasTestedEdge) { r2[startEdgeIdx] = newStartEdge; maxValue = count_common_roads(r2); if (!treeEdge[newStartEdge]) maxValue++; r2[startEdgeIdx] = startEdge; } // printf("maxValue = %d\n",maxValue); for(int anEdge: cycle) { int temp; if (testedEdge[anEdge]) { temp = treeEdge[anEdge]? maxValue:maxValue-1; } else { r2[startEdgeIdx] = anEdge; testedEdge[anEdge] = true; temp = count_common_roads(r2); maxValue = max(maxValue,temp); } result.push_back(temp); } // printf("result: "); for(int elem: result) printf("%d ",elem); printf("\n"); for(int j=0; j<result.size(); j++) if (result[j] == maxValue) treeEdge[cycle[j]] = 1; r2[startEdgeIdx] = startEdge; // printf("testedEdge: "); for(bool elem: testedEdge) printf("%d ",elem); printf("\n"); // printf("treeEdge: "); for(int elem: treeEdge) printf("%d ",elem); printf("\n\n"); } } for(int i=0; i<m; i++) if (treeEdge[i]) r.push_back(i); // printf("r: "); for(int elem: r) printf("%d ",elem); printf("\n"); return r; } void dfs(int parent, int now, std::vector<int>& visit, std::vector<vector<int>>& edgeL) { visit[now]=1; for(int elem: edgeL[now]) if (elem!=parent && !visit[elem]) dfs(now,elem,visit,edgeL); return; } bool isTree(std::vector<int>& r, std::vector<int>& u, std::vector<int>& v) { int n = r.size()+1; std::vector<vector<int>> edgeL(n); for(int i=0; i<n-1; i++) { int s = u[r[i]], e = v[r[i]]; edgeL[s].push_back(e); edgeL[e].push_back(s); } vector<int> visit(n,0); dfs(-1,u[r[0]],visit,edgeL); for(int i=0; i<n; i++) if(!visit[i]) return false; return true; } bool selectEdges(int cnt, int start, std::vector<int>& r, std::vector<int>& u, std::vector<int>& v){ int n = r.size()+1, m = u.size(); if (cnt == n-1){ if(isTree(r,u,v) && count_common_roads(r)== n-1) return true; else return false; } for(int i=start; i<m; i++){ r[cnt] = i; if (selectEdges(cnt+1,i+1,r,u,v)) return true; } return false; } std::vector<int> subtask1(int n, std::vector<int>& u, std::vector<int>& v) { std::vector<int> r(n-1), zero(n-1,-1); if (selectEdges(0,0,r,u,v)) return r; else return zero; } std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { return subtask3(n,u,v); // if (isSubtask1(n)) return subtask1(n,u,v); }

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<int> subtask3(int, std::vector<int>&, std::vector<int>&)':
simurgh.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             for(int j=0; j<result.size(); j++)
      |                          ~^~~~~~~~~~~~~~
simurgh.cpp: In function 'void dfs(int, int, std::vector<int>&, std::vector<std::vector<int> >&)':
simurgh.cpp:123:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  123 |     for(int elem: edgeL[now])
      |     ^~~
simurgh.cpp:126:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  126 |  return;
      |  ^~~~~~
#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...