Submission #1075909

#TimeUsernameProblemLanguageResultExecution timeMemory
1075909edogawa_somethingSimurgh (IOI17_simurgh)C++17
51 / 100
147 ms26716 KiB
#include "simurgh.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vii; typedef pair<ll,ll> pii; #define F first #define S second #define all(v) v.begin(),v.end() #define pb push_back const ll M=250000; vector<pii> adj[M]; bool vis[M]; vii sp; void dfs(ll x) { vis[x]=1; for(auto it:adj[x]) { if(vis[it.F]) continue; sp.pb(it.S); dfs(it.F); } } struct dsu { ll sz[250],pa[250]; void init(ll x) { for(int i=0;i<x;i++) sz[i]=1,pa[i]=i; } ll get(ll x) { if(x==pa[x]) return x; return pa[x]=get(pa[x]); } void unite(ll x,ll y) { x=get(x),y=get(y); if(x==y) return; if(sz[x]>sz[y]) swap(x,y); pa[x]=y; sz[y]+=sz[x]; } bool same(ll x,ll y) { return get(x)==get(y); } }d; ll cnt[M],cc[M]; bool a[M]; set<ll>s; vector<int> find_roads(int n, std::vector<int> u, std::vector<int> vv) { for(int i=0;i<u.size();i++) adj[u[i]].pb({vv[i],i}),adj[vv[i]].pb({u[i],i}); dfs(0); vector<int>ans,res; for(int i=0;i<u.size();i++) vis[i]=0; ll cntq=0; for(auto it:sp) { s.clear(); ans.clear(); d.init(n); vii v; for(auto itt:sp) { if(itt!=it) ans.pb(itt),d.unite(u[itt],vv[itt]); } for(int i=0;i<u.size();i++) cnt[i]=0; for(int i=0;i<u.size();i++) { if(!d.same(u[i],vv[i])&&!vis[i]) { ans.pb(i); assert(cntq<30000); ll x=count_common_roads(ans); cntq++; cnt[ans.back()]=x; s.insert(x); v.pb(i); ans.pop_back(); } } if(s.size()==1) { bool cc[2]; cc[0]=cc[1]=0; for(int i=0;i<u.size();i++) { if(!d.same(u[i],vv[i])&&vis[i]&&!cc[a[i]]) { cc[a[i]]=1; ans.pb(i); assert(cntq<30000); s.insert(count_common_roads(ans)); cntq++; ans.pop_back(); } } } for(auto it:v) { vis[it]=1; if(cnt[it]==*s.rbegin()) { a[it]=1; } } } for(int i=0;i<u.size();i++) if(a[i])res.pb(i); assert(res.size()==n-1); assert(cntq<=30000); return res; } /* 5 10 0 1 0 2 0 3 0 4 1 2 1 3 1 4 2 3 2 4 3 4 3 6 8 9 */

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<u.size();i++)
      |               ~^~~~~~~~~
simurgh.cpp:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int i=0;i<u.size();i++)
      |               ~^~~~~~~~~
simurgh.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
simurgh.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<u.size();i++) {
      |                 ~^~~~~~~~~
simurgh.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |       for(int i=0;i<u.size();i++) {
      |                   ~^~~~~~~~~
simurgh.cpp:103:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   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:105:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |   assert(res.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...