Submission #73485

#TimeUsernameProblemLanguageResultExecution timeMemory
73485SmsSSimurgh (IOI17_simurgh)C++14
0 / 100
39 ms2640 KiB
#include<bits/stdc++.h> #define pb push_back using namespace std; #define for2(a,b,c) for(int a = b; a < c; a++) #include "simurgh.h" const int maxn = 510; int adj[maxn][maxn]; bool seen[maxn]; bool burn[maxn]; std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { std::vector<int> res(n - 1); int m = u.size(); srand(10); vector<int> sh(n); for2(i,0,n) sh[i] = i; random_shuffle(sh.begin(),sh.end()); for2(i,0,m){ ///////////// continue; /////////////// u[i] = sh[u[i]]; v[i] = sh[v[i]]; } for2(i,0,m) adj[u[i]][v[i]] = adj[v[i]][u[i]] = i; vector<int> tree; tree.pb(0); seen[0] = 1; int rep = 0; while(tree.size() != n){ // cout << rep << endl; // for(auto x : res) cout <<x << ' '; // cout << endl; for(auto x : tree)if(!burn[x]){ burn[x] = 1; int cnt = rep; for2(i,0,n)if(!seen[i]) res[cnt++] = adj[i][x]; int get = (count_common_roads(res)); if(rep == get) continue; // cout << x << endl; int last = -1; cnt = rep; for2(i,0,n) if(!seen[i]){ if(last != -1){ res[cnt++] = adj[i][last]; } last = i; } // for(auto x : res) cout << x << ' '; // cout << endl; vector<int> c; int mx = 0; for2(i,0,n)if(!seen[i]){ res[cnt] = adj[i][x]; c.pb(count_common_roads(res)); // cout << c.back() << endl; mx = max(mx,c.back()); } // cout << mx << endl; cnt = 0; for2(i,0,n) if(!seen[i]){ if(c[cnt++] == mx){ tree.pb(i); seen[i] = 1; res[rep] = adj[i][x]; rep++; } } } } return res; }

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(tree.size() != n){
        ~~~~~~~~~~~~^~~~
#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...