oj.uz

Submission #409321

# Submission time Handle Problem Language Result Execution time Memory
409321 2021-05-20T15:00:27 Z MKopchev Highway Tolls (IOI18_highway) C++14
100 / 100
 315 ms 17716 KB 
#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][2];

queue<int> q;

vector<int> mem_U,mem_V;

int solve(int from,int id,vector<int> valid_edges,vector<int> blocked)
{
    //cout<<"solve "<<from<<" "<<id<<" "<<valid_edges.size()<<endl;

    set<int> in={};
    for(auto w:valid_edges)in.insert(w);

    int was=valid_edges.size();

    for(auto w:valid_edges)
    {
        int p=mem_U[w];
        int q=mem_V[w];

        if(dist[p][id]>dist[q][id])swap(p,q);
    }

    /*
    for(int i=0;i<mem_U.size();i++)
        if(in.count(i)==0)valid_edges.push_back(i);
    */

    //for(auto w:valid_edges)cout<<dist[mem_U[w]]<<" "<<dist[mem_V[w]]<<endl;

    int ok=was-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;

        for(auto w:blocked)cur[w]=1;

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

    //cout<<"valid= ";for(auto w:valid_edges)cout<<w<<" -> "<<mem_U[w]<<" "<<mem_V[w]<<" , ";cout<<endl;

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

    //system("pause");
    //exit(0);

    if(ok==-1)return from;

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

    //cout<<"dist= "<<dist[u][id]<<" "<<dist[v][id]<<endl;

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

    if(dist[u][id]<dist[v][id])return v;
    return u;
}

int dist_help[nmax][2];

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);

    //cout<<"d= "<<mem_d/A<<endl;

    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;

    /*
    q.push(from);

    set<int> in={};

    while(q.size())
    {
        dist[from]=0;

        int node=q.front();

        q.pop();

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

                valid_edges.push_back(w.second);
                in.insert(w.second);

                q.push(w.first);
            }
    }
    */

    memset(dist,-1,sizeof(dist));

    int outp[2];

    for(int which=0;which<2;which++)
    {
        vector<int> valid_edges={};

        int from=(which==0?U[ok]:V[ok]);

        dist[from][which]=0;

        q.push(from);

        //cout<<which<<" "<<from<<endl;

        while(q.size())
        {

        int node=q.front();

        //cout<<"node= "<<node<<endl;

        q.pop();

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

                //valid_edges.push_back(w.second);

                q.push(w.first);
            }
        }
        //outp[which]=solve(from,valid_edges);
    }

    memset(dist_help,-1,sizeof(dist_help));

    for(int which=0;which<2;which++)
    {
        vector<int> valid_edges={};

        int from=(which==0?U[ok]:V[ok]);

        dist_help[from][which]=0;

        q.push(from);

        //cout<<which<<" "<<from<<endl;

        vector<int> blocked={};

        while(q.size())
        {

        int node=q.front();

        q.pop();



        for(auto w:adj[node])
            if(dist[w.first][which]<dist[w.first][!which])
                {
                    if(dist_help[w.first][which]==-1)
                    {
                        dist_help[w.first][which]=dist_help[node][which]+1;

                        valid_edges.push_back(w.second);

                        q.push(w.first);
                    }
                    else if(dist_help[w.first][which]==dist_help[node][which]+1)blocked.push_back(w.second);

            }
            else if(w.second!=ok)blocked.push_back(w.second);
        }

        /*
        for(int i=0;i<n;i++)
            for(auto j:adj[i])
                if(i<j.first&&dist[i][which]==dist[j.first][which])blocked.push_back(j.second);
        */

        outp[which]=solve(from,which,valid_edges,blocked);
    }

    int s=outp[0];
    int t=outp[1];

    //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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4168 KB Output is correct
2 Correct 3 ms 4196 KB Output is correct
3 Correct 3 ms 4168 KB Output is correct
4 Correct 3 ms 4168 KB Output is correct
5 Correct 3 ms 4168 KB Output is correct
6 Correct 3 ms 4168 KB Output is correct
7 Correct 3 ms 4168 KB Output is correct
8 Correct 3 ms 4168 KB Output is correct
9 Correct 3 ms 4168 KB Output is correct
10 Correct 4 ms 4168 KB Output is correct
11 Correct 3 ms 4168 KB Output is correct
12 Correct 3 ms 4168 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4256 KB Output is correct
2 Correct 19 ms 5448 KB Output is correct
3 Correct 178 ms 15404 KB Output is correct
4 Correct 179 ms 15264 KB Output is correct
5 Correct 215 ms 15320 KB Output is correct
6 Correct 200 ms 15336 KB Output is correct
7 Correct 221 ms 15264 KB Output is correct
8 Correct 215 ms 15300 KB Output is correct
9 Correct 208 ms 15340 KB Output is correct
10 Correct 204 ms 15372 KB Output is correct
11 Correct 227 ms 12776 KB Output is correct
12 Correct 218 ms 13752 KB Output is correct
13 Correct 186 ms 14720 KB Output is correct
14 Correct 207 ms 14408 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5276 KB Output is correct
2 Correct 31 ms 6344 KB Output is correct
3 Correct 54 ms 7540 KB Output is correct
4 Correct 161 ms 13004 KB Output is correct
5 Correct 176 ms 13076 KB Output is correct
6 Correct 124 ms 13788 KB Output is correct
7 Correct 153 ms 14536 KB Output is correct
8 Correct 132 ms 13328 KB Output is correct
9 Correct 131 ms 13520 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4296 KB Output is correct
2 Correct 21 ms 5148 KB Output is correct
3 Correct 131 ms 13112 KB Output is correct
4 Correct 208 ms 15340 KB Output is correct
5 Correct 220 ms 15340 KB Output is correct
6 Correct 217 ms 15336 KB Output is correct
7 Correct 207 ms 15420 KB Output is correct
8 Correct 173 ms 15336 KB Output is correct
9 Correct 225 ms 15000 KB Output is correct
10 Correct 199 ms 15416 KB Output is correct
11 Correct 183 ms 14800 KB Output is correct
12 Correct 183 ms 14060 KB Output is correct
13 Correct 211 ms 13752 KB Output is correct
14 Correct 239 ms 13220 KB Output is correct
15 Correct 215 ms 15440 KB Output is correct
16 Correct 191 ms 15352 KB Output is correct
17 Correct 201 ms 14448 KB Output is correct
18 Correct 174 ms 14708 KB Output is correct
19 Correct 177 ms 15396 KB Output is correct
20 Correct 206 ms 14388 KB Output is correct
21 Correct 175 ms 15512 KB Output is correct
22 Correct 135 ms 15628 KB Output is correct
23 Correct 187 ms 13028 KB Output is correct
24 Correct 138 ms 13064 KB Output is correct
25 Correct 214 ms 14460 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5284 KB Output is correct
2 Correct 25 ms 5448 KB Output is correct
3 Correct 218 ms 15540 KB Output is correct
4 Correct 252 ms 14832 KB Output is correct
5 Correct 297 ms 16804 KB Output is correct
6 Correct 287 ms 16568 KB Output is correct
7 Correct 276 ms 15672 KB Output is correct
8 Correct 267 ms 15012 KB Output is correct
9 Correct 186 ms 13764 KB Output is correct
10 Correct 234 ms 13884 KB Output is correct
11 Correct 191 ms 14900 KB Output is correct
12 Correct 289 ms 14420 KB Output is correct
13 Correct 228 ms 14948 KB Output is correct
14 Correct 238 ms 15520 KB Output is correct
15 Correct 243 ms 16372 KB Output is correct
16 Correct 214 ms 13028 KB Output is correct
17 Correct 146 ms 15296 KB Output is correct
18 Correct 197 ms 15480 KB Output is correct
19 Correct 189 ms 15512 KB Output is correct
20 Correct 197 ms 15660 KB Output is correct
21 Correct 295 ms 16972 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5292 KB Output is correct
2 Correct 19 ms 5448 KB Output is correct
3 Correct 227 ms 13684 KB Output is correct
4 Correct 201 ms 14256 KB Output is correct
5 Correct 260 ms 15040 KB Output is correct
6 Correct 295 ms 15024 KB Output is correct
7 Correct 193 ms 15904 KB Output is correct
8 Correct 254 ms 15752 KB Output is correct
9 Correct 267 ms 13768 KB Output is correct
10 Correct 303 ms 15516 KB Output is correct
11 Correct 251 ms 14832 KB Output is correct
12 Correct 295 ms 14996 KB Output is correct
13 Correct 176 ms 14968 KB Output is correct
14 Correct 232 ms 13888 KB Output is correct
15 Correct 231 ms 14960 KB Output is correct
16 Correct 209 ms 13816 KB Output is correct
17 Correct 185 ms 14976 KB Output is correct
18 Correct 224 ms 13804 KB Output is correct
19 Correct 250 ms 14284 KB Output is correct
20 Correct 241 ms 15972 KB Output is correct
21 Correct 264 ms 15536 KB Output is correct
22 Correct 290 ms 15308 KB Output is correct
23 Correct 263 ms 14952 KB Output is correct
24 Correct 266 ms 15152 KB Output is correct
25 Correct 251 ms 16020 KB Output is correct
26 Correct 256 ms 15804 KB Output is correct
27 Correct 196 ms 15448 KB Output is correct
28 Correct 174 ms 15444 KB Output is correct
29 Correct 161 ms 16084 KB Output is correct
30 Correct 200 ms 15788 KB Output is correct
31 Correct 200 ms 15504 KB Output is correct
32 Correct 156 ms 15404 KB Output is correct
33 Correct 173 ms 15960 KB Output is correct
34 Correct 194 ms 15436 KB Output is correct
35 Correct 154 ms 15360 KB Output is correct
36 Correct 146 ms 15412 KB Output is correct
37 Correct 157 ms 15684 KB Output is correct
38 Correct 154 ms 15924 KB Output is correct
39 Correct 315 ms 17008 KB Output is correct
40 Correct 275 ms 16984 KB Output is correct
41 Correct 251 ms 17716 KB Output is correct
42 Correct 252 ms 16404 KB Output is correct