제출 #1210389

#제출 시각아이디문제언어결과실행 시간메모리
1210389tosivanmakSimurgh (IOI17_simurgh)C++20
100 / 100
86 ms21716 KiB
#include<bits/stdc++.h> #include "simurgh.h" using namespace std; #define ll long long // static int MAXQ = 30000; // static int n, m, q = 0; // static vector<int> u, v; // static vector<bool> goal; // static void wrong_answer() { // cout<<"No\n"; // exit(0); // } // static bool is_valid(const vector<int>& r) { // if(int(r.size()) != n - 1) // return false; // for(int i = 0; i < n - 1; i++) // if (r[i] < 0 || r[i] >= m) // return false; // return true; // } // static int _count_common_roads_internal(const vector<int>& r) { // if(!is_valid(r)){ // wrong_answer(); // } // int common = 0; // for(int i = 0; i < n - 1; i++) { // bool is_common = goal[r[i]]; // if (is_common) // common++; // } // return common; // } // int count_common_roads(const vector<int>& r) { // q++; // if(q > MAXQ) // wrong_answer(); // return _count_common_roads_internal(r); // } vector<ll>adj[505]; struct Edge{ ll u,v,id; }; // int count_common_roads(int[] r) struct DSU{ vector<ll>fa,siz; void init(ll n){ fa.resize(n+5); siz.resize(n+5); for(int i=0;i<n+5;i++){ fa[i]=i,siz[i]=1; } } ll root(ll x){ if(fa[x]==x)return x; return fa[x]=root(fa[x]); } void unite(ll u, ll v){ u=root(u); v=root(v); if(siz[u]<siz[v])swap(u,v); fa[v]=u; siz[u]+=siz[v]; } }; int Query(vector<int>r){ // cout<<"Lag "<<r.size()<<endl; int val=count_common_roads(r); return val; } enum Type {Normal, Royal, Undefined}; struct Graph{ vector<Edge>edge,tedge; vector<vector<pair<ll,ll> > >adj,tadj; vector<vector<ll> >res; vector<ll>dep,fa,highest,eid; vector<bool>vis; vector<Type>type; vector<ll>tree; int tree_val; void init(ll n){ adj.resize(n+5); tadj.resize(n+5); vis.resize(n+5); dep.resize(n+5); fa.resize(n+5); type.resize(n*n+5); highest.resize(n+5); eid.resize(n+5); res.resize(n+5); for(int i=0;i<n+5;i++){ res[i].resize(n+5); } for(int i=0;i<n+5;i++){ highest[i]=-1; eid[i]=-1; } for(int i=0;i<n*n+5;i++){ type[i]=Type::Undefined; } } void add_edge(ll u, ll v, ll id){ edge.push_back({u,v,id}); adj[u].push_back({v,id}); adj[v].push_back({u,id}); res[u][v]=res[v][u]=id; } void dfs(ll s){ vis[s]=1; for(auto& [u,id]: adj[s]){ if(!vis[u]){ dep[u]=dep[s]+1; dfs(u); tadj[s].push_back({u,id}); tadj[u].push_back({s,id}); fa[u]=s; tedge.push_back({s,u,id}); tree.push_back(id); } } } void construct(ll s){ vis[s]=1; highest[s]=dep[s]; eid[s]=-1; for(auto& [u,id]: adj[s]){ if(!vis[u]){ construct(u); if(highest[u]<highest[s]){ highest[s]=highest[u]; eid[s]=eid[u]; } } else{ if(u==fa[s])continue; if(dep[u]<highest[s]){ highest[s]=dep[u]; eid[s]=id; } } } } void clear(ll n){ for(int i=0;i<=n;i++)vis[i]=0; } void build_induced_subtree(ll n){ dep[0]=1; dfs(0); clear(n); construct(0); clear(n); // cout<<"Constructed\n"; // for(int i=0;i<tree.size();i++){ // cout<<tree[i]<<" "; // } // cout<<'\n'; } vector<ll>edge_list; int pull(ll x, int add){ vector<int>qrylist; if(x==-1){ for(auto& u: tree){ qrylist.push_back(u); } return Query(qrylist); } else{ qrylist.push_back(add); for(auto& u: tree){ if(u!=x){ qrylist.push_back(u); } } // cout<<qrylist.size()<<'\n'; // for(auto& u: qrylist){ // cout<<u<<" "; // } return Query(qrylist); } } void build(ll u, ll v){ while(dep[u]!=dep[v]){ edge_list.push_back(res[u][fa[u]]); u=fa[u]; } } void process(ll edge_id){ vector<pair<ll,ll> >alls; ll cnt=0; ll wrt; for(auto& u: edge_list){ if(type[u]!=Type::Undefined){ cnt++; if(cnt==1){ wrt=pull(u,edge_id); if(type[u]==Type::Royal){ if(tree_val==wrt)type[edge_id]=Type::Royal; else type[edge_id]=Type::Normal; } else{ if(tree_val==wrt)type[edge_id]=Type::Normal; else type[edge_id]=Type::Royal; } } continue; } alls.push_back({pull(u,edge_id),u}); } sort(alls.begin(),alls.end()); // add 1, neutral, minus 1 if(type[edge_id]==Type::Undefined){ if(alls[0].first==alls[alls.size()-1].first){ if(tree_val==alls[0].first){ for(int i=0;i<alls.size();i++){ type[alls[i].second]=Type::Normal; } type[edge_id]=Type::Normal; } else{ for(int i=0;i<alls.size();i++){ type[alls[i].second]=Type::Royal; } type[edge_id]=Type::Normal; } } else{ ll mini=alls[0].first; ll maxi=alls[alls.size()-1].first; if(mini<tree_val){ type[edge_id]=Type::Normal; for(int i=0;i<alls.size();i++){ if(alls[i].first<tree_val)type[alls[i].second]=Type::Royal; else type[alls[i].second]=Type::Normal; } } else{ type[edge_id]=Type::Royal; for(int i=0;i<alls.size();i++){ if(alls[i].first==tree_val)type[alls[i].second]=Type::Royal; else type[alls[i].second]=Type::Normal; } } } } else{ for(int i=0;i<alls.size();i++){ if(alls[i].first==tree_val){ type[alls[i].second]=type[edge_id]; } else{ if(type[edge_id]==Type::Royal)type[alls[i].second]=Type::Normal; else type[alls[i].second]=Type::Royal; } } } edge_list.clear(); } void find_tree_edge(ll n){ tree_val=pull(-1,-1); for(int i=1;i<n;i++){ ll req=res[i][fa[i]]; if(type[req]!=Type::Undefined)continue; if(highest[i]!=dep[i]){ auto [u,v,id]=edge[eid[i]]; // cout<<"Debug : "<<i<<" "<<u<<" "<<v<<" "<<eid[i]<<'\n'; if(dep[u]<dep[v]){ swap(u,v); } build(u,v); process(id); } else{ ll req=res[i][fa[i]]; type[req]=Type::Royal; } } } ll qry(ll n, vector<Edge>& lst, ll l, ll r){ DSU d; d.init(n); ll royals=0; // tedge vector<int>used; for(int i=l;i<=r;i++){ auto& [u,v,id]=lst[i]; d.unite(u,v); used.push_back(id); } for(auto& [u,v,id]: tedge){ if(d.root(u)!=d.root(v)){ used.push_back(id); d.unite(u,v); royals+=(type[id]==Type::Royal); } } // cout<<used.size()<<endl; // for(int i=0;i<(int)used.size();i++){ // cout<<used[i]<<' '; // } return Query(used)-royals; } void dc(ll n, ll l, ll r, ll rem, vector<Edge>& lst){ if(l==r){ type[lst[l].id]=Type::Royal; return; } ll mid=(l+r)>>1; ll lrem=qry(n,lst,l,mid); ll rrem=rem-lrem; if(lrem!=0){ dc(n,l,mid,lrem,lst); } if(rrem!=0){ dc(n,mid+1,r,rrem,lst); } } void deal(vector<Edge>lst, ll n){ DSU d; d.init(n); ll royals=0; // tedge vector<int>used; for(auto& [u,v,id]: lst){ d.unite(u,v); used.push_back(id); } for(auto& [u,v,id]: tedge){ if(d.root(u)!=d.root(v)){ used.push_back(id); d.unite(u,v); royals+=(type[id]==Type::Royal); } } // cout<<used.size()<<endl; // for(int i=0;i<used.size();i++){ // cout<<used[i]<<' '; // } ll val=Query(used); if(val==royals){ for(int i=0;i<(int)lst.size();i++){ type[lst[i].id]=Type::Normal; } return; } else{ dc(n,0,(int)lst.size()-1,val-royals,lst); for(int i=0;i<(int)lst.size();i++){ if(type[lst[i].id]==Type::Undefined){ type[lst[i].id]=Type::Normal; } } return; } } void remaining(ll n){ DSU dd[n+5]; vector<Edge>lst[n+5]; for(int i=1;i<=n;i++)dd[i].init(n); for(auto& [u,v,id]: edge){ if(type[id]==Type::Undefined){ ll l=1,r=n; while(l<r){ ll mid=(l+r)>>1; if(dd[mid].root(u)!=dd[mid].root(v))r=mid; else l=mid+1; } lst[l].push_back({u,v,id}); dd[l].unite(u,v); } } for(int i=1;i<=n;i++){ if(lst[i].size()){ deal(lst[i],n); } } } }; vector<int>find_roads(int n, vector<int>u, vector<int>v){ int m=u.size(); for(int i=0;i<m;i++){ adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]); } Graph g; g.init(n); for(int i=0;i<m;i++){ g.add_edge(u[i],v[i],i); } g.build_induced_subtree(n); // cout<<"Check\n"; g.find_tree_edge(n); // cout<<"Check\n"; // for(int i=0;i<(int)u.size();i++){ // cout<<g.type[i]<<'\n'; // } // cout<<'\n'; g.remaining(n); vector<int>ans; for(int i=0;i<(int)u.size();i++){ if(g.type[i]==Type::Royal){ // cout<<g.type[i]<<'\n'; ans.push_back(i); } } // cout<<ans.size()<<"\n"; // for(auto& u: ans){ // cout<<u<<"\n"; // } return ans; } // int main() { // assert(2 == scanf("%d %d", &n, &m)); // u.resize(m); // v.resize(m); // for(int i = 0; i < m; i++) // assert(2 == scanf("%d %d", &u[i], &v[i])); // goal.resize(m, false); // for(int i = 0; i < n - 1; i++) { // int id; // assert(1 == scanf("%d", &id)); // goal[id] = true; // } // vector<int> res = find_roads(n, u, v); // if(_count_common_roads_internal(res) != n - 1) // wrong_answer(); // cout<<"Yes\n"; // return 0; // }
#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...