Submission #294566

#	Time	Username	Problem	Language	Result	Execution time	Memory
294566		Gurban	통행료 (IOI18_highway)	C++17	6 / 100	256 ms	14620 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;
vi col;
ll init;
queue<pii>q;
int dis[maxn],us[maxn];
pii par[maxn];
vector<pii> adj[maxn],E[maxn];
vi v[3],cl;

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

int bin(int tp){
	int l=1,r=sz(v[tp])-1,md,jog=0;
	while(l <= r){
		md=(l+r)/2;
		
		for(int i = 0;i < M;i++) col[i]=0;
		for(auto i : cl) col[i] = 1;
		for(int i = md;i <= r;i++) if(par[v[tp][i]].ff!=-1) col[par[v[tp][i]].ff]=1;

		if(ask(col) > init) jog=md,l=md+1;
		else r=md-1;
	}
	return v[tp][jog];
}

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,jog=M-1;
	while(l < r){
		
		md = (l+r)/2;
		for(int i = 0;i <= md;i++) col[i]=1;
		for(int i = md+1;i < M;i++) col[i]=0;

		ll now=ask(col);
		if(now > init) r=md-1,jog=md;
		else l=md+1;
	}

	r=jog;
	// cout<<U[r]<<' '<<V[r]<<'\n';

	for(int i=0;i<N;i++) dis[i]=mod;
	dis[U[r]]=0;
	dis[V[r]]=0;

	par[U[r]].ff=-1;
	par[V[r]].ff=-1;

	bfs(U[r],V[r]);

	// for(int i = 0;i < N;i++) cout<<par[i].ff<<' ';
	// cout<<'\n';

	us[r]=1;
	for(int i = 0;i < M;i++) if(!us[i]) cl.pb(i);

	// for(auto i : v[0]) cout<<i<<' ';
	// cout<<" --\n";
	// for(auto i : v[1]) cout<<i<<' ';
	// cout<<'\n';

	int ans=bin(0);
	int ans1=bin(1);
	// cout<<ans<<' '<<ans1<<'\n';
	answer(ans,ans1);
}

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