Submission #1053473

#TimeUsernameProblemLanguageResultExecution timeMemory
1053473UnforgettableplSimurgh (IOI17_simurgh)C++17
30 / 100
3095 ms2200 KiB
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; vector<int> find_roads(int n, vector<int> u, vector<int> v){ int m = u.size(); set<int> graph; vector<set<pair<int,int>>> adj(n); vector<bool> confirmed(m); function<bool(int,int,int)> finder = [&](int x,int p,int tar) { if(x==tar)return true; for(auto[v,idx]:adj[x])if(v!=p)if(finder(v,x,tar))return true; return false; }; auto differential = [&](int x){ stack<int> edges; function<bool(int,int)> dfs = [&](int xx,int p) { if(xx==v[x])return true; for(auto[v,idx]:adj[xx])if(v!=p){ edges.emplace(idx); if(dfs(v,xx))return true; edges.pop(); } return false; }; dfs(u[x],-1); if(edges.empty()) { graph.insert(x); adj[u[x]].emplace(v[x],x); adj[v[x]].emplace(u[x],x); } vector<int> finaledges; while(!edges.empty()) { finaledges.emplace_back(edges.top()); edges.pop(); } vector<int> sameas; bool included = false; for(int&i:finaledges) { if(confirmed[i])continue; auto base = count_common_roads(vector(graph.begin(),graph.end())); graph.erase(i); graph.insert(x); auto diff = count_common_roads(vector(graph.begin(),graph.end())); graph.erase(x); graph.insert(i); if(diff==base) { sameas.emplace_back(i); continue; } if(diff>base) { included=true; graph.erase(i); adj[u[i]].erase({v[i],i}); adj[v[i]].erase({u[i],i}); } break; } if(included) { graph.insert(x); adj[u[x]].emplace(v[x],x); adj[v[x]].emplace(u[x],x); confirmed[x]=true; for(int&i:sameas)confirmed[i]=true; } else { for(int&i:sameas) { graph.erase(i); adj[u[i]].erase({v[i],i}); adj[v[i]].erase({u[i],i}); } } }; vector<bool> visited(m); for(int i=0;i<m;i++) { if(graph.size()!=n-1) { for(int j=i;j<m;j++) { if(visited[j])continue; if(finder(u[j],-1,v[j])==false) { visited[j]=true; graph.insert(j); adj[u[j]].emplace(v[j],j); adj[v[j]].emplace(u[j],j); } } } if(visited[i])continue; differential(i); } return vector(graph.begin(), graph.end()); }

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:75:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |   if(graph.size()!=n-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...