Submission #1077065

#TimeUsernameProblemLanguageResultExecution timeMemory
1077065guanexSimurgh (IOI17_simurgh)C++14
13 / 100
67 ms4700 KiB
#include "simurgh.h" #include<bits/stdc++.h> using namespace std; typedef pair<int, int> ii; typedef long long ll; typedef vector<ii> vii; typedef vector<ll> vll; typedef pair<long long, long long> pll; typedef pair<char, int> ci; typedef pair<string, int> si; typedef long double ld; typedef vector<int> vi; typedef vector<string> vs; #define pb push_back #define fi first #define se second #define whole(v) v.begin(), v.end() #define rwhole(v) v.rbegin(), v.rend() #define inf INT_MAX/2 #define fro front vi ans; vector<vii> x(501); ii fa[501]; int rs[125001]; int vis[501]; vi tree; int z; int cn = 0; void df(int no, int f,int ideje){ if(ideje != -1){ tree.pb(ideje); } fa[no] = ii(f, ideje); vis[no] = 1; for(auto e:x[no]){ if(vis[e.fi]){ continue; } df(e.fi, no, e.se); } } void dfs(int no,int ideje){ vis[no] = 1; //cout << "currently " << no << '\n'; for(auto e:x[no]){ if(e.se == ideje || vis[e.fi] == 2){ continue; } if(vis[e.fi] == 1){ //cout << ".."<< e.fi << endl; int f = no; while(f != e.fi){ int ff = f; f = fa[f].fi; if(rs[fa[ff].se] != -1){ vi tre = tree; for(int i = 0; i < tre.size(); ++i){ if(tre[i] == fa[ff].se){ tre[i] = e.se; } } //cout << f << " " << ff << " " << fa[ff].se << endl; for(auto e:tre){ //cout << e << " "; } //cout << endl; int g = count_common_roads(tre); cn++; assert ( cn < 29999 ); //cout << g << endl; if(g == z){ rs[e.se] = rs[fa[ff].se]; }else if(g == z+1){ rs[e.se] = 1; }else{ rs[e.se] = 0; } f = e.fi; } } if(rs[e.se] == -1){ f = no; while(f != e.fi){ int ff = f; f = fa[f].fi; vi tre = tree; //cout << f << " " << ff << " " << fa[ff].se << endl; for(int i = 0; i < tre.size(); ++i){ if(tre[i] == fa[ff].se){ tre[i] = e.se; } } for(auto e:tre){ //cout << e << " "; } //cout << endl; int g = count_common_roads(tre); cn++; assert ( cn < 29999 ); //cout << g << endl; if(g == z){ continue; }else if(g == z+1){ rs[e.se] = 1; rs[fa[ff].se] = 0; f = e.fi; }else{ rs[e.se] = 0; rs[fa[ff].se] = 1; f = e.fi; } } } f = no; while(f != e.fi){ int ff = f; f = fa[f].fi; if(rs[fa[ff].se] != -1){ continue; } vi tre = tree; for(int i = 0; i < tre.size(); ++i){ if(tre[i] == fa[ff].se){ tre[i] = e.se; } } //cout << f << " " << ff << " " << fa[ff].se << endl; for(auto e:tre){ //cout << e << " "; } //cout << endl; int g = count_common_roads(tre); cn++; assert ( cn < 29999 ); //cout << g << endl; if(g == z){ rs[fa[ff].se] = rs[e.se]; }else if(g == z+1){ rs[e.se] = 1; rs[fa[ff].se] = 0; f = e.fi; }else{ rs[e.se] = 0; rs[fa[ff].se] = 1; f = e.fi; } } //cout << endl << endl; continue; } dfs(e.fi, e.se); } vis[no] = 2; } std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { for(int i = 0; i < u.size(); ++i){ x[u[i]].pb(ii(v[i], i)); x[v[i]].pb(ii(u[i], i)); } fa[0] = ii(0, -1); df(0, 0, -1); memset(vis, 0, sizeof vis); memset(rs, -1, sizeof rs); z = count_common_roads(tree); if(z == n-1){ return tree; } dfs(0, -1); ////cout << 1 << endl; for(auto e:tree){ if(rs[e] == -1){ rs[e] = 1; } } for(int i = 0; i < 125001; ++i){ if(rs[i] == 1) ans.pb(i); } assert(ans.size() <= n - 1); for(auto e:ans){ //cout << e << endl; } return ans; }

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:62:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                     for(int i = 0; i < tre.size(); ++i){
      |                                    ~~^~~~~~~~~~~~
simurgh.cpp:68:30: warning: unused variable 'e' [-Wunused-variable]
   68 |                     for(auto e:tre){
      |                              ^
simurgh.cpp:93:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                     for(int i = 0; i < tre.size(); ++i){
      |                                    ~~^~~~~~~~~~~~
simurgh.cpp:98:30: warning: unused variable 'e' [-Wunused-variable]
   98 |                     for(auto e:tre){
      |                              ^
simurgh.cpp:127:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |                 for(int i = 0; i < tre.size(); ++i){
      |                                ~~^~~~~~~~~~~~
simurgh.cpp:133:26: warning: unused variable 'e' [-Wunused-variable]
  133 |                 for(auto e:tre){
      |                          ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for(int i = 0; i < u.size(); ++i){
      |                    ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp:185:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  185 |     assert(ans.size() <= n - 1);
      |            ~~~~~~~~~~~^~~~~~~~
simurgh.cpp:186:14: warning: unused variable 'e' [-Wunused-variable]
  186 |     for(auto e:ans){
      |              ^
#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...