Submission #715302

#	Time	Username	Problem	Language	Result	Execution time	Memory
715302		lam	Highway Tolls (IOI18_highway)	C++14	5 / 100	148 ms	25472 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
int n,m,w1,w2,dist;
vector <ii> adj[maxn];
ii e[maxn];
int d[maxn]; ii par[maxn];
int side[maxn];
int dnc(int lx, int rx, vector<int> &dau)
{
    if (lx==rx) return lx;
    int mid=(lx+rx)/2;
    for (int i=lx; i<=mid; i++) dau[i] = 1;
    int temp = ask(dau);
//    for (int i:dau) cout<<i<<' '; cout<<" = "<<temp<<'\n';
    bool check = temp  > dist;
    for (int i=lx; i<=mid; i++) dau[i] = 0;
    if (check) return  dnc(lx,mid,dau);
    else return dnc(mid+1,rx,dau);
}
int trace(int lx, int rx, vector <int>&nodes, vector <int> &dau)
{
    if (lx==rx) return nodes[lx];
    int mid=(lx+rx)/2;
    for (int i=lx; i<=mid; i++) dau[par[nodes[i]].ss] = 1;
    bool check = (ask(dau) > dist);
    for (int i=lx; i<=mid; i++) dau[par[nodes[i]].ss] = 0;
    if (check) return trace(lx,mid,nodes,dau);
    else return trace(mid+1,rx,nodes,dau);

}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  m=U.size(); n=N; w1=A; w2=B;
  for (int i=0; i<m; i++) e[i].ff=U[i], e[i].ss = V[i], adj[e[i].ff].push_back({e[i].ss,i}), adj[e[i].ss].push_back({e[i].ff,i});
  vector <int> dau(m,0);
  dist=ask(dau);
//   cerr<<dist<<endl;
  int idx = dnc(0,m-1,dau);
//  cerr<<idx<<endl;
  fill_n(d,n,-1);
  int u=e[idx].ff; int v=e[idx].ss;
  d[u]=d[v]=0; par[u] = par[v] = {-1,-1};
  dau[idx] = -1;
  queue<int> q;
  q.push(u); q.push(v);
  side[u] = 1; side[v] = 2;
  while (!q.empty())
  {
      int u=q.front(); q.pop();
      for (ii i:adj[u])
      {
          int v=i.ff; int id = i.ss;
          if (d[v]==-1)
          {
              par[v] = {u,id};
              side[v] = side[u];
              d[v] = d[u]+1;
//              cerr<<u<<" - "<<v<<endl;
              dau[id] = side[v];
              q.push(v);
          }
      }
  }
  vector <int> tmp(m,0);
  for (int i=0; i<m; i++) if (dau[i]==0) tmp[i]=1;
  for (int i=0; i<m; i++) if (dau[i]==1) tmp[i]=1;
//  for (int i:tmp) cerr<<i<<' '; cerr<<" = "<<ask(tmp)<<endl;
  int du = (ask(tmp)-dist)/(w2-w1);
  for (int i=0; i<m; i++) if (dau[i]==1) tmp[i]=0;
  for (int i=0; i<m; i++) if (dau[i]==2) tmp[i]=1;
  int dv = (ask(tmp)-dist)/(w2-w1);
  for (int i=0; i<m; i++) if (dau[i]==2) tmp[i]=0;
//  cerr<<u<<' '<<du<<" & "<<v<<' '<<dv<<endl;
  vector <int> nodes;
  for (int i=0; i<n; i++) if (side[i]==1&&d[i]==du) nodes.push_back(i);
//  for (int i=0; i<n; i++) cerr<<d[i]<<','<<side[i]<<' '; cerr<<endl;
  int s,t;
//  cerr<<nodes.size()<<endl;
  if (du==0) s=u;
  else s=trace(0,nodes.size()-1,nodes,tmp);
  nodes.clear();
  for (int i=0; i<n; i++) if (side[i]==2&&d[i]==dv) nodes.push_back(i);
  if (dv==0) t=v;
  else t=trace(0,nodes.size()-1,nodes,tmp);
  answer(s,t);
}

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