Submission #733284

#	Time	Username	Problem	Language	Result	Execution time	Memory
733284		PoonYaPat	Highway Tolls (IOI18_highway)	C++14	0 / 100	14 ms	3284 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) {

    for (int i=0; i<m; ++i) w[i]=0;
    for (auto s : adj[start]) w[s.second]=1;
    if (ask(w)!=Base) return 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);


    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:73:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i=0; i<edge.size(); ++i) {
      |                       ~^~~~~~~~~~~~

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