제출 #1290329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290329		PlayVoltz	통행료 (IOI18_highway)	C++20	100 / 100	131 ms	19764 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, m, k, TT=0;
vector<int> booga;
vector<vector<pii> > adj;
vector<vector<int> > dj;

int calc(vector<pii> ord){
	int low=-1, high=ord.size();
	while (low+1<high){
		int mid=(low+high)/2;
		vector<signed> temp(m, 0);
		for (int i=0; i<m; ++i)if (booga[i])temp[i]=1;
		for (int i=mid; i<ord.size(); ++i)temp[ord[i].se]=1;
		int ress=ask(temp);
		if (k==ress)high=mid;
		else low=mid;
	}
	if (low==-1)return -1;
	return ord[low].fi;
}

bool custom(pii a, pii b){
	return dj[TT][a.fi]<dj[TT][b.fi];
}

void find_pair(signed N, vector<signed> u, vector<signed> v, signed a, signed b){
	n=N, m=u.size();
	adj.clear();
	dj.clear();
	booga.clear();
	booga.resize(m, 1);
	adj.resize(n);
	vector<pii> ord;
	vector<signed> temp(m, 0);
	k=ask(temp);
	for (int i=0; i<m; ++i){
		adj[u[i]].pb(mp(v[i], i));
		adj[v[i]].pb(mp(u[i], i));
	}
	int low=0, high=m;
	while (low+1<high){
		int mid=(low+high)/2;
		vector<signed> temp(m, 0);
		for (int i=0; i<mid; ++i)temp[i]=1;
		if (ask(temp)==k)low=mid;
		else high=mid;
	}
	vector<vector<int> > par(2, vector<int>(n, -1));
	dj.resize(2, vector<int>(n, -1));
	queue<pii> q;
	dj[0][u[low]]=dj[1][v[low]]=0;
	booga[low]=0;
	q.push(mp(0, u[low]));
	q.push(mp(1, v[low]));
	while (q.size()){
		int node=q.front().se, p=q.front().fi;
		q.pop();
		for (auto num:adj[node])if (dj[p][num.fi]==-1)dj[p][num.fi]=dj[p][node]+1, q.push(mp(p, num.fi)), par[p][num.fi]=num.se;
	}
	vector<int> ans, ooga;
	ooga.pb(u[low]);
	ooga.pb(v[low]);
	for (int i=0; i<n; ++i){
		if (dj[0][i]<dj[1][i]&&par[0][i]!=-1)booga[par[0][i]]=0;
		if (dj[1][i]<dj[0][i]&&par[1][i]!=-1)booga[par[1][i]]=0;
	}
	for (int i=0; i<2; ++i){
		vector<pii> ord;
		for (int j=0; j<n; ++j)if (dj[i][j]<dj[!i][j]&&par[i][j]!=-1)ord.pb(mp(j, par[i][j]));
		TT=i;
		sort(ord.begin(), ord.end(), custom);
		int res=calc(ord);
		if (res==-1)ans.pb(ooga[i]);
		else ans.pb(res);
	}
	answer(ans[0], ans[1]);
}

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