Submission #408862

#	Time	Username	Problem	Language	Result	Execution time	Memory
408862		MKopchev	Highway Tolls (IOI18_highway)	C++14	51 / 100	187 ms	10272 KiB

highway

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

constexpr int MAX_NUM_CALLS = 100;
constexpr long long INF = 1LL << 61;

int N, M, A, B, S, T;
std::vector<int> U, V;
std::vector<std::vector<std::pair<int, int>>> graph;

bool answered, wrong_pair;
int num_calls;

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

void wrong_answer(const char *MSG) {
  printf("Wrong Answer: %s\n", MSG);
  exit(0);
}

}  // namespace

long long ask(const std::vector<int> &w) {
  if (++num_calls > MAX_NUM_CALLS) {
    wrong_answer("more than 100 calls to ask");
  }
  if (w.size() != (size_t)M) {
    wrong_answer("w is invalid");
  }
  for (size_t i = 0; i < w.size(); ++i) {
    if (!(w[i] == 0 || w[i] == 1)) {
      wrong_answer("w is invalid");
    }
  }

  std::vector<bool> visited(N, false);
  std::vector<long long> current_dist(N, INF);
  std::queue<int> qa, qb;
  qa.push(S);
  current_dist[S] = 0;
  while (!qa.empty() || !qb.empty()) {
    int v;
    if (qb.empty() ||
        (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
      v = qa.front();
      qa.pop();
    } else {
      v = qb.front();
      qb.pop();
    }
    if (visited[v]) {
      continue;
    }
    visited[v] = true;
    long long d = current_dist[v];
    if (v == T) {
      return d;
    }
    for (auto e : graph[v]) {
      int vv = e.first;
      int ei = e.second;
      if (!visited[vv]) {
        if (w[ei] == 0) {
          if (current_dist[vv] > d + A) {
            current_dist[vv] = d + A;
            qa.push(vv);
          }
        } else {
          if (current_dist[vv] > d + B) {
            current_dist[vv] = d + B;
            qb.push(vv);
          }
        }
      }
    }
  }
  return -1;
}

void answer(int s, int t) {
  if (answered) {
    wrong_answer("answered not exactly once");
  }

  if (!((s == S && t == T) || (s == T && t == S))) {
    wrong_pair = true;
  }

  answered = true;
}
*/
const int nmax=1e5+42;

vector< pair<int,int> > adj[nmax];

int n,m,a,b;

vector<int> idle;

long long mem_d;

int dist[nmax];

queue<int> q;

vector<int> mem_U,mem_V;

int solve(int from,int blocked)
{
    memset(dist,-1,sizeof(dist));

    dist[from]=0;

    vector<int> valid_edges={};

    q.push(from);

    while(q.size())
    {
        int node=q.front();

        q.pop();

        for(auto w:adj[node])
            if(w.second!=blocked&&dist[w.first]==-1)
            {
                dist[w.first]=dist[node]+1;

                valid_edges.push_back(w.second);

                q.push(w.first);
            }
    }

    if(valid_edges.size()==0)return from;

    int ok=valid_edges.size()-1,not_ok=-2;

    while(ok-not_ok>1)
    {
        int av=(ok+not_ok)/2;

        vector<int> cur=idle;

        for(int j=av+1;j<valid_edges.size();j++)
            cur[valid_edges[j]]=1;

        if(ask(cur)==mem_d)ok=av;
        else not_ok=av;
    }

    //cout<<"valid= ";for(auto w:valid_edges)cout<<w<<" ";cout<<endl;

    //cout<<"ok= "<<ok<<endl;

    if(ok==-1)return from;

    int u=mem_U[valid_edges[ok]];
    int v=mem_V[valid_edges[ok]];

    //cout<<"u= "<<u<<" v= "<<v<<endl;

    if(dist[u]<dist[v])return v;
    return u;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    n=N;
    m=U.size();

    a=A;
    b=B;

    for(int i=0;i<m;i++)idle.push_back(0);

    for(int i=0;i<m;i++)
    {
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }

    mem_U=U;
    mem_V=V;

    mem_d=ask(idle);

    int ok=m-1,not_ok=-1;

    while(ok-not_ok>1)
    {
        int av=(ok+not_ok)/2;

        vector<int> me=idle;
        for(int j=0;j<=av;j++)me[j]=1;

        if(ask(me)>mem_d)ok=av;
        else not_ok=av;
    }

    //cout<<"edge "<<U[ok]<<" "<<V[ok]<<endl;

    int s=solve(U[ok],ok);
    int t=solve(V[ok],ok);

    //cout<<"s= "<<s<<" t= "<<t<<endl;

    answer(s,t);
}

/*
int main() {
  N = read_int();
  M = read_int();
  A = read_int();
  B = read_int();
  S = read_int();
  T = read_int();
  U.resize(M);
  V.resize(M);
  graph.assign(N, std::vector<std::pair<int, int>>());
  for (int i = 0; i < M; ++i) {
    U[i] = read_int();
    V[i] = read_int();
    graph[U[i]].push_back({V[i], i});
    graph[V[i]].push_back({U[i], i});
  }

  answered = false;
  wrong_pair = false;
  num_calls = 0;
  find_pair(N, U, V, A, B);
  if (!answered) {
    wrong_answer("answered not exactly once");
  }
  if (wrong_pair) {
    wrong_answer("{s, t} is wrong");
  }
  printf("Accepted: %d\n", num_calls);
  return 0;
}
*/

Compilation message (stderr)

highway.cpp: In function 'int solve(int, int)':
highway.cpp:155:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for(int j=av+1;j<valid_edges.size();j++)
      |                        ~^~~~~~~~~~~~~~~~~~~

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