Submission #103476

#TimeUsernameProblemLanguageResultExecution timeMemory
103476figter001Simurgh (IOI17_simurgh)C++17
30 / 100
3028 ms3968 KiB
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int nax = 510; int dsu[nax]; int m,n; vector<pair<int,int>> g[nax]; vector<int> u,v; int find(int u){ return u == dsu[u] ? u : dsu[u] = find(dsu[u]); } bool good(vector<int> ans){ for(int i=0;i<n;i++) dsu[i] = i; for(int i=0;i<ans.size();i++){ int id = ans[i]; int a = u[id]; int b = v[id]; if(find(a) == find(b)) continue; dsu[find(b)] = find(a); } for(int i=0;i<n;i++) if(find(i) != find(0)) return 0; return 1; } vector<int> find_roads(int N, vector<int> U, vector<int> V) { vector<int> ans; u = U; v = V; n = N; m = u.size(); for(int i=0;i<n;i++) dsu[i] = i; int lst; for(int i=0;i<m;i++){ int a = u[i]; int b = v[i]; g[a].push_back({b,i}); g[b].push_back({a,i}); if(find(a) == find(b)) continue; ans.push_back(i); dsu[find(b)] = find(a); } lst = count_common_roads(ans); for(int i=0;i<ans.size();i++){ int id = ans[i]; int a = u[id]; int b = v[id]; for(int j=0;j<m;j++){ ans[i] = j; if(good(ans) == 1){ int r = count_common_roads(ans); if(r < lst){ ans[i] = id; break; } if(r > lst){ lst = r; break; } } ans[i] = id; } } // for(int i : ans) // printf("%d ", i); // printf("\n"); return ans; }

Compilation message (stderr)

simurgh.cpp: In function 'bool good(std::vector<int>)':
simurgh.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ans.size();i++){
              ~^~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:59:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ans.size();i++){
              ~^~~~~~~~~~~
simurgh.cpp:61:7: warning: unused variable 'a' [-Wunused-variable]
   int a = u[id];
       ^
simurgh.cpp:62:7: warning: unused variable 'b' [-Wunused-variable]
   int b = v[id];
       ^
#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...