Submission #733309

#	Time	Username	Problem	Language	Result	Execution time	Memory
733309		PoonYaPat	Highway Tolls (IOI18_highway)	C++14	51 / 100	174 ms	10780 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
 
int n,m,u,v,disU[90001],disV[90001];
ll Base,a,b;
vector<int> w;
vector<pii> adj[90001],Edge;
bool vis[90001];
 
void F(int* dis, int start) {
    memset(vis,0,sizeof(vis));
    for (int i=0; i<n; ++i) dis[i]=1e9;
 
    queue<int> q;
    q.push(start);
    dis[start]=0;
 
    while (!q.empty()) {
        int node=q.front();
        q.pop();
 
        if (vis[node]) continue;
        vis[node]=true;
 
        for (auto s : adj[node]) {
            if (dis[s.first]>dis[node]+1) {
                dis[s.first]=dis[node]+1;
                q.push(s.first);
            }
        }
    }
}
 
int f(int* dis1, int* dis2, int start) {
    memset(vis,0,sizeof(vis));
 
    queue<int> q;
    vector<int> edge;
    q.push(start);
    vis[start]=true;
 
    while (!q.empty()) {
        int node=q.front();
        q.pop();
 
        for (auto s : adj[node]) {
            if (vis[s.first]) continue;
            if (dis1[s.first]>=dis2[s.first]) continue;
            vis[s.first]=true;
            edge.push_back(s.second);
            q.push(s.first);
        }
    }
 
    vector<int> temp;
    for (int i=0; i<m; ++i) temp.push_back(1);
    for (auto s : edge) temp[s]=0;
    ll base=ask(temp);
  
    if (base%b==0 && (base/b)*a==Base) return start;
 
    int l=0, r=edge.size()-1;
    while (l<r) {
        int mid=(l+r)/2;
 
        for (int i=0; i<edge.size(); ++i) {
            if (i<=mid) temp[edge[i]]=0;
            else temp[edge[i]]=1;
        }
 
        if (ask(temp)==base) r=mid;
        else l=mid+1;
    }
 
    if (dis1[Edge[edge[l]].first]<dis1[Edge[edge[l]].second]) return Edge[edge[l]].second;
    else return Edge[edge[l]].first;
}
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    m=U.size();
    n=N; a=A; b=B;
 
    for (int i=0; i<m; ++i) {
        w.push_back(0);
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
        Edge.push_back({U[i],V[i]});
    }
    Base=ask(w);
 
    int l=0, r=m-1;
    while (l<r) {
        int mid=(l+r)/2;
        for (int i=0; i<m; ++i) {
            if (i<=mid) w[i]=0;
            else w[i]=1;
        }
        if (ask(w)==Base) r=mid;
        else l=mid+1;
    }
 
    u=U[l];
    v=V[l];
 
    F(disU,u);
    F(disV,v);
 
    answer(f(disU,disV,u),f(disV,disU,v));
}

Compilation message (stderr)

highway.cpp: In function 'int f(int*, int*, int)':
highway.cpp:69:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int i=0; i<edge.size(); ++i) {
      |                       ~^~~~~~~~~~~~

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