Submission #804287

#TimeUsernameProblemLanguageResultExecution timeMemory
804287ngraceSimurgh (IOI17_simurgh)C++14
30 / 100
3065 ms3380 KiB
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; #define ve vector #define ll long long #define ii pair<int, int> #define fi first #define se second int N; set<int> ans; int edgeInd[240][240]; struct DSU{ int par[500]; int si=0; DSU(int siz){ si=siz; reset(); } void reset(){ for(int i=0; i<si; i++) par[i]=i; } int root(int x) { return (x==par[x]) ? x : par[x]=root(par[x]); } void doUnion(int a, int b){ par[root(a)]=root(b); } }; ve<pair<ii, int>> baseTree; bool treeVis[500]; void treeDFS(int x){ treeVis[x]=true; for(int i=0; i<N; i++){ if(edgeInd[x][i]==-1) continue; if(!treeVis[i]){ baseTree.push_back({{x, i}, edgeInd[x][i]}); treeDFS(i); } } } ve<int> cycleVis(240, 0); ve<int> cycle; int cycleIter=0; int cycleStart; bool cycleDFS(int x, int par){ if(x==cycleStart){ cycle.push_back(x); return true; } if(cycleVis[x]==cycleIter) return false; cycleVis[x] = cycleIter; cycle.push_back(x); for(int i=0; i<N; i++){ if(edgeInd[x][i]==-1 || i==par) continue; if(cycleDFS(i, x)) return true; } cycle.pop_back(); return false; } bool findCycle(int a, int b){ cycleIter++; cycle = {a}; cycleVis[a] = cycleIter; cycleStart = a; return cycleDFS(b, a); } int cutTime=0; int cutIter=0; ve<int> cutVis(240, false); ve<int> firstTime(240, -1); ve<int> lowTime(240, -1); int numCut=0; void cutDFS(int cur, int par){ cutVis[cur]=cutIter; firstTime[cur] = lowTime[cur] = cutTime++; for(int i=0; i<N; i++){ if(edgeInd[cur][i]==-1 || i==par) continue; if(cutVis[i]==cutIter) lowTime[cur] = min(lowTime[cur], firstTime[i]); else{ cutDFS(i, cur); lowTime[cur] = min(lowTime[cur], lowTime[i]); if(lowTime[i] > firstTime[cur]) { numCut++; } } } } int findCutEdges(){ cutIter++; cutTime=0; numCut=0; cutDFS(0, 0); return numCut; } std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { N = n; if(n==2){ ve<int> res = {0}; return res; } for(int i=0; i<240; i++){ for(int j=0; j<240; j++){ edgeInd[i][j] = -1; } } for(int i=0; i < u.size(); i++){ edgeInd[u[i]][v[i]] = i; edgeInd[v[i]][u[i]] = i; } treeDFS(0); int origCut = findCutEdges(); ve<ve<bool>> known(N, ve<bool>(N, false)); set<ii> dontbother; for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ if(edgeInd[i][j]==-1 || known[i][j]) continue; if(findCycle(i, j)){ ve<int> tree2; ve<int> treeInd(N); DSU inTree(N); int missing = cycle.size()-2; for(int c=0; c<cycle.size()-1; c++){ int a=cycle[c], b=cycle[c+1]; inTree.doUnion(a, b); tree2.push_back(edgeInd[a][b]); treeInd[c] = c; if(c==missing){ treeInd[c] = -1; tree2.pop_back(); } } for(auto it:baseTree){ int a=it.fi.fi, b=it.fi.se; if(inTree.root(a)!=inTree.root(b)){ tree2.push_back(it.se); inTree.doUnion(a,b); } } int ma=0; ve<int> cou(cycle.size()-1, -1); for(int c=0; c<cycle.size()-1; c++){ int a=cycle[c], b=cycle[c+1]; if(c!=missing){ int newa=cycle[missing], newb=cycle[missing+1]; tree2[treeInd[c]] = edgeInd[newa][newb]; treeInd[missing] = treeInd[c]; treeInd[c] = -1; missing = c; } cou[c] = count_common_roads(tree2); ma = max(ma, cou[c]); } for(int c=0; c<cycle.size()-1; c++){ int a=cycle[c], b=cycle[c+1]; known[a][b] = known[b][a] = true; if(cou[c]<ma && ans.find(edgeInd[a][b]) == ans.end()){ ans.insert(edgeInd[a][b]); } } for(int c=0; c<cycle.size()-1; c++){ int a=cycle[c], b=cycle[c+1]; if(dontbother.find({a,b}) != dontbother.end()) continue; int tmp = edgeInd[a][b]; edgeInd[a][b] = edgeInd[b][a] = -1; if(findCutEdges()!=origCut){ edgeInd[a][b] = edgeInd[b][a] = tmp; dontbother.insert({a,b}); } } } else{ ans.insert(edgeInd[i][j]); known[i][j] = known[j][i] = true; } } } ve<int> res; for(int i:ans) res.push_back(i); return res; }

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:117:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for(int i=0; i < u.size(); i++){
      |               ~~^~~~~~~~~~
simurgh.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for(int c=0; c<cycle.size()-1; c++){
      |                  ~^~~~~~~~~~~~~~~
simurgh.cpp:155:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for(int c=0; c<cycle.size()-1; c++){
      |                  ~^~~~~~~~~~~~~~~
simurgh.cpp:156:10: warning: unused variable 'a' [-Wunused-variable]
  156 |      int a=cycle[c], b=cycle[c+1];
      |          ^
simurgh.cpp:156:22: warning: unused variable 'b' [-Wunused-variable]
  156 |      int a=cycle[c], b=cycle[c+1];
      |                      ^
simurgh.cpp:168:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |     for(int c=0; c<cycle.size()-1; c++){
      |                  ~^~~~~~~~~~~~~~~
simurgh.cpp:175:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for(int c=0; c<cycle.size()-1; c++){
      |                  ~^~~~~~~~~~~~~~~
#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...