Submission #293903

#	Time	Username	Problem	Language	Result	Execution time	Memory
293903		Gurban	통행료 (IOI18_highway)	C++17	0 / 100	270 ms	16876 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 1e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int M;
ll init;
int dis[maxn],L[maxn],par[maxn];
vector<pii> adj[maxn],E[maxn],v;
queue<int>q;
vi col;

void bfs(int nd){
	q.push(nd);
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(auto i : adj[x]){
			if(dis[i.ff] > dis[x]+1){
				dis[i.ff]=dis[x]+1;
				q.push(i.ff);
				E[x].pb({i.ff,i.ss});
				E[i.ff].pb({x,i.ss});
			}
		}
	}
}

void dfs(int nd,int pr){
	L[nd]=L[pr]+1;
	v.pb({L[nd],nd});
	for(auto i : E[nd]){
		if(i.ff != pr){
			par[i.ff]=i.ss;
			dfs(i.ff,nd);
		}
	}
}

int bin(){
	int l=0,r=sz(v)-1,md;
	while(l <= r){
		md=(l+r)/2;

		// cout<<md<<'\n';
		
		for(int i = 0;i < M;i++) col[i]=0;
		
		for(int i = md;i <= r;i++) col[par[v[i].ss]]=1;
		// cout<<ask(col)<<'\n';
		// break;
		if(ask(col) > init) l=md+1;
		else r=md-1;
	}
	return l-1;
}

void find_pair(int N, vi U, vi V, int A, int B) {
	M = sz(U); col.resize(M);
	for(int i = 0;i < M;i++){
		adj[U[i]].pb({V[i],i});
		adj[V[i]].pb({U[i],i});
	}
	init = ask(col);
	int l = 0,r = M-1,md;
	while(l < r){
		md = (l+r)/2;
		for(int i = 0;i < M;i++) col[i]=0;
		
		for(int i=l;i<=md;i++) col[i] = 1;
		
		if(ask(col) > init) r=md;
		else l=md+1;
	}
	
	for(int i=0;i<N;i++) dis[i]=mod;
	dis[U[r]]=0;

	bfs(U[r]);
	dfs(V[r],U[r]);
	sort(all(v));
	int ans = v[bin()].ss;
	
	v.clear(); memset(L,0,sizeof(L));
	dfs(U[r],V[r]);
	sort(all(v));
	
	// for(auto i : v) cout<<i.ff<<' '<<i.ss<<'\n';
	int ans1=v[bin()].ss;

	// cout<<ans<<' '<<ans1<<'\n';
	
	answer(ans,ans1);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31