제출 #442885

#제출 시각아이디문제언어결과실행 시간메모리
442885vanic통행료 (IOI18_highway)C++14
0 / 100
47 ms13136 KiB
#include "highway.h" #include <vector> #include <iostream> #include <cmath> #include <algorithm> #include <queue> #include <cstring> using namespace std; typedef long long ll; const int maxn=1e5, maxm=2e5; int m, a, b, n; vector < int > ms[maxn]; vector < int > ms1[maxn]; pair < int, int > edge[maxm]; vector < int > Q; ll poc; int nadji(int l, int r){ if(l==r-1){ return l; } int mid=(l+r)/2; for(int i=l; i<mid; i++){ Q[i]=1; } ll val=ask(Q); if(val>poc){ for(int i=l; i<mid; i++){ Q[i]=0; } return nadji(l, mid); } else{ return nadji(mid, r); } } int dist[2][maxn]; void bfs(int x, int ind){ queue < int > q; q.push(x); dist[ind][x]=0; while(!q.empty()){ x=q.front(); q.pop(); for(int i=0; i<(int)ms[x].size(); i++){ if(dist[ind][ms[x][i]]==-1){ dist[ind][ms[x][i]]=dist[ind][x]+1; q.push(ms[x][i]); } } } } int col[maxn]; vector < int > sta[maxn]; vector < int > sta1[maxn]; int bio[maxn]; void bfs1(int x){ queue < int > q; q.push(x); memset(bio, -1, sizeof(bio)); bio[x]=0; while(!q.empty()){ x=q.front(); q.pop(); for(int i=0; i<(int)ms[x].size(); i++){ if(bio[ms[x][i]]==-1 && col[ms[x][i]]==col[x]){ bio[ms[x][i]]=bio[x]+1; sta[x].push_back(ms[x][i]); sta1[x].push_back(ms1[x][i]); // cout << x << ' ' << ms[x][i] << ' ' << ms1[x][i] << endl; sta[ms[x][i]].push_back(x); sta1[ms[x][i]].push_back(ms1[x][i]); q.push(ms[x][i]); } } } } vector < int > red; void dfs(int x, int prosl){ for(int i=0; i<(int)sta[x].size(); i++){ if(sta[x][i]!=prosl){ red.push_back(sta1[x][i]); dfs(sta[x][i], x); } } } ll maksi; int rijesi(int l, int r){ if(l==r-1){ return l; } int mid=(l+r)/2; for(int i=l; i<mid; i++){ if(red[i]==-1){ continue; } Q[red[i]]=1; } if(ask(Q)==maksi){ return rijesi(l, mid); } else{ return rijesi(mid, r); } } void find_pair(int N, vector<int> u, vector<int> v, int A, int B) { m = u.size(); n=N; a=A; b=B; for(int i=0; i<m; i++){ edge[i]={u[i], v[i]}; ms[u[i]].push_back(v[i]); ms[v[i]].push_back(u[i]); ms1[u[i]].push_back(i); ms1[v[i]].push_back(i); } Q.resize(m, 0); poc=ask(Q); int x=nadji(0, m); memset(dist[0], -1, sizeof(dist[0])); memset(dist[1], -1, sizeof(dist[1])); bfs(edge[x].first, 0); bfs(edge[x].second, 1); for(int i=0; i<n; i++){ if(dist[0][i]<dist[1][i]){ col[i]=1; } } red.push_back(-1); bfs1(edge[x].first); dfs(edge[x].first, -1); for(int i=1; i<(int)red.size(); i++){ Q[red[i]]=1; } maksi=ask(Q); for(int i=1; i<(int)red.size(); i++){ Q[red[i]]=0; } /* cout << "red "; for(int i=0; i<(int)red.size(); i++){ cout << red[i] << ' '; } cout << endl;*/ int y=red[rijesi(0, red.size())]; int sol1, sol2; if(y==-1){ sol1=edge[x].first; } else if(bio[edge[y].first]>bio[edge[y].second]){ sol1=edge[y].first; } else{ sol1=edge[y].second; } /* for(int i=0; i<n; i++){ sta[i].clear(); sta1[i].clear(); }*/ bfs1(edge[x].second); red.clear(); red.push_back(-1); dfs(edge[x].second, -1); for(int i=1; i<(int)red.size(); i++){ Q[red[i]]=1; } maksi=ask(Q); for(int i=1; i<(int)red.size(); i++){ Q[red[i]]=0; } /* cout << "red2 "; for(int i=0; i<(int)red.size(); i++){ cout << red[i] << ' '; } cout << endl;*/ y=red[rijesi(0, red.size())]; if(y==-1){ sol2=edge[x].second; } else if(bio[edge[y].first]>bio[edge[y].second]){ sol2=edge[y].first; } else{ sol2=edge[y].second; } // cout << sol1 << ' ' << sol2 << ' ' << x << endl; answer(sol1, sol2); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...