| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1291221 | Math4Life2020 | Highway Tolls (IOI18_highway) | C++20 | 0 ms | 0 KiB |
#include "tolls.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
mt19937_64 gen;
pair<vector<ll>,vector<ll>> dijk(ll src, ll N, vector<int> U, vector<int> V, vector<int> W, ll A, ll B) {
//min time, edge index of origin
ll M = U.size();
vector<array<ll,3>> adj[N];
for (ll i=0;i<M;i++) {
if (W[i]==0) {
// //cout << "0U[i]="<<U[i]<<"\n";
// //cout << "V[i]="<<V[i]<<"\n";
adj[U[i]].push_back({V[i],A,i});
adj[V[i]].push_back({U[i],A,i});
} else if (W[i]==1) {
// //cout << "1U[i]="<<U[i]<<"\n";
// //cout << "V[i]="<<V[i]<<"\n";
adj[U[i]].push_back({V[i],B,i});
adj[V[i]].push_back({U[i],B,i});
} else {
//cout << "DIJK CALL INVALID\n"; exit(0);
}
}
//exit(0);
vector<bool> prc(N,0);
set<array<ll,3>> q0;
q0.insert({0,src,-1});
vector<ll> ans(N,-1);
vector<ll> org(N,-1);
while (q0.size()!=0) {
auto A0 = *q0.begin(); q0.erase(q0.begin());
ll x = A0[1];
ll t = A0[0];
if (prc[x]) {
continue;
} else {
prc[x]=1;
ans[x]=t;
org[x]=A0[2];
for (auto A1: adj[x]) {
q0.insert({A1[1]+t,A1[0],A1[2]});
}
}
}
return {ans,org};
}
void find_pair(int N, vector<int> U, vector<int> V, int A0, int B0) {
//cout << "A,B="<<A0<<","<<B0<<"\n";
ll M = U.size();
ll A = A0; ll B = B0;
ll val0 = ask(vector<int>(M,0));
ll mmin = 0;
ll mmax = M; //max # of segments that can be blocked without affecting ans
while (mmin!=mmax) {
ll mqry = (mmin+mmax+1)/2;
vector<int> vq0(M,0);
for (ll x=0;x<mqry;x++) {
vq0[x]=1;
}
if (ask(vq0)==val0) {
mmin = mqry;
} else {
mmax = mqry-1;
}
}
ll plen = val0/A;
//critical segment is at index mmin
vector<int> mmc(M,0);
for (ll x=0;x<mmin;x++) {
mmc[x]=1;
//cout << "deleted segments: x="<<x<<"\n";
//cout << "vals: U,V="<<U[x]<<","<<V[x]<<"\n";
}
ll c = U[mmin]; ll d = V[mmin];
//cout << "c,d="<<c<<","<<d<<"\n";
auto cm1 = dijk(c,N,U,V,mmc,A,B);
auto cm0 = dijk(c,N,U,V,vector<int>(M,0),A,B);
auto dm1 = dijk(d,N,U,V,mmc,A,B);
auto dm0 = dijk(d,N,U,V,vector<int>(M,0),A,B);
vector<int> mfv(M,1);
mfv[mmin]=0;
vector<array<ll,3>> cndS,cndT; //candidates for S/T: {+dist,x,src edge}
for (ll x=0;x<N;x++) {
if (cm1.first[x]==cm0.first[x] && cm0.first[x]<dm0.first[x]) {
if (x!=c) {
mfv[(cm1.second[x])]=0;
}
cndS.push_back({cm0.first[x],x,cm0.second[x]});
}
if (dm1.first[x]==dm0.first[x] && dm0.first[x]<cm0.first[x]) {
if (x!=d) {
mfv[dm1.second[x]]=0;
}
cndT.push_back({dm0.first[x],x,dm0.second[x]});
}
}
sort(cndS.begin(),cndS.end());
for (auto A0: cndS) {
//cout << "cndS: "<<A0[0]<<","<<A0[1]<<","<<A0[2]<<"\n";
}
sort(cndT.begin(),cndT.end());
for (auto A0: cndT) {
//cout << "cndT: "<<A0[0]<<","<<A0[1]<<","<<A0[2]<<"\n";
}
ll SL = cndS.size(); ll TL = cndT.size();
ll smin = 0; ll smax = SL-1;
while (smin!=smax) {
ll sqry = (smin+smax+1)/2;
vector<int> qry = mfv;
for (ll x=sqry;x<SL;x++) {
qry[cndS[x][2]]=1;
}
if (ask(qry)==val0) {
smax = sqry-1;
} else {
smin = sqry;
}
}
ll tmin = 0; ll tmax = TL-1;
while (tmin!=tmax) {
ll tqry = (tmin+tmax+1)/2;
vector<int> qry = mfv;
for (ll x=tqry;x<TL;x++) {
qry[cndT[x][2]]=1;
}
if (ask(qry)==val0) {
tmax = tqry-1;
} else {
tmin = tqry;
}
}
ll S = cndS[smin][1];
ll T = cndT[tmin][1];
//cout << "S="<<S<<", T="<<T<<"\n";
answer(S,T);
}