oj.uz

Submission #441914

# Submission time Handle Problem Language Result Execution time Memory
441914 2021-07-06T14:37:52 Z keta_tsimakuridze Highway Tolls (IOI18_highway) C++14
51 / 100
 310 ms 262148 KB 
#include "highway.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int Q = 2e5 + 5;
/*
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
///#include "highway.h"
 
namespace {
 
const int MAX_NUM_CALLS = 100;
const 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 ( int t = 0; t <  graph[v].size(); t++) {
    	pair<int,int> e = graph[v][t];
      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;
} */
/////////////////////////////////////////
int timer,out[Q],pos[Q],up[Q],c[Q];
vector<int> x;
vector<pair<int,int> > V[Q];
void dfs(int u,int p) {
	
	for(int i=0;i<V[u].size();i++) {
		if(V[u][i].f != p)  up[V[u][i].f] = V[u][i].s,c[V[u][i].f] = u,dfs(V[u][i].f,u);
	}
	timer++;
	pos[timer] = u;
}
void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B) {
  for(int i=0;i<u.size();i++){
  	V[u[i]].push_back({v[i],i});
  	V[v[i]].push_back({u[i],i});
  }
  dfs(0,-1);  
  x.resize(u.size());
  long long D = ask(x);
  int l = 1, r = n - 1,S = -1, T = 0;
  while(l<=r) {
  	int mid = (l+r)/2;
  	
  	for(int i=1;i<n;i++) {
  		if(i < mid) x[up[pos[i]]] = 1;
  		else x[up[pos[i]]] = 0;
	}
	long long d = ask(x); 
	if(d == D) { 
		S = pos[mid]; 
		l = mid + 1;
	}
	else r = mid - 1;
  }
  for(int i = 0; i<n;i++) reverse(V[i].begin(),V[i].end());
  timer = 0;
  dfs(0,-1);
	l = 1, r = n;
while(l<=r) {
  	int mid = (l+r)/2;
  	
  	for(int i=1;i<n;i++) {
  		if(i < mid) x[up[pos[i]]] = 1;
  		else x[up[pos[i]]] = 0;
	}
	long long d = ask(x); 
	if(d == D) { 
		T = pos[mid]; 
		l = mid + 1;
	}
	else r = mid - 1;
  }
  for(int i=0;i<u.size();i++) x[i] = 1;
  int e = S;
  while(e) { 
  	x[up[e]] = 0;
  	e = c[e];
  }
  if(ask(x) == D) {
  	D /= A;
  	T = S;
  	while(D--) {
  		T = c[T];
	  }
  }
  //cout<<S<<" "<<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 'void dfs(int, int)':
highway.cpp:120:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(int i=0;i<V[u].size();i++) {
      |              ~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:127:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for(int i=0;i<u.size();i++){
      |               ~^~~~~~~~~
highway.cpp:167:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |   for(int i=0;i<u.size();i++) x[i] = 1;
      |               ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5064 KB Output is correct
2 Correct 21 ms 5584 KB Output is correct
3 Correct 226 ms 11204 KB Output is correct
4 Correct 200 ms 11220 KB Output is correct
5 Correct 183 ms 11252 KB Output is correct
6 Correct 241 ms 11232 KB Output is correct
7 Correct 225 ms 11196 KB Output is correct
8 Correct 219 ms 11304 KB Output is correct
9 Correct 189 ms 11200 KB Output is correct
10 Correct 234 ms 11260 KB Output is correct
11 Correct 240 ms 12108 KB Output is correct
12 Correct 195 ms 12596 KB Output is correct
13 Correct 225 ms 12140 KB Output is correct
14 Correct 236 ms 11648 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6216 KB Output is correct
2 Correct 40 ms 7480 KB Output is correct
3 Correct 45 ms 8660 KB Output is correct
4 Correct 126 ms 16384 KB Output is correct
5 Correct 129 ms 16272 KB Output is correct
6 Correct 144 ms 16272 KB Output is correct
7 Correct 122 ms 16380 KB Output is correct
8 Correct 170 ms 16276 KB Output is correct
9 Correct 168 ms 16356 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5064 KB Output is correct
2 Correct 20 ms 5564 KB Output is correct
3 Correct 163 ms 9832 KB Output is correct
4 Correct 239 ms 11248 KB Output is correct
5 Correct 221 ms 11196 KB Output is correct
6 Correct 225 ms 11192 KB Output is correct
7 Correct 222 ms 11280 KB Output is correct
8 Correct 214 ms 11188 KB Output is correct
9 Correct 214 ms 11296 KB Output is correct
10 Correct 227 ms 11272 KB Output is correct
11 Correct 203 ms 11660 KB Output is correct
12 Correct 245 ms 12796 KB Output is correct
13 Correct 240 ms 12244 KB Output is correct
14 Correct 204 ms 12632 KB Output is correct
15 Correct 209 ms 11200 KB Output is correct
16 Correct 220 ms 11204 KB Output is correct
17 Correct 201 ms 12468 KB Output is correct
18 Correct 184 ms 12068 KB Output is correct
19 Correct 181 ms 11192 KB Output is correct
20 Correct 194 ms 13308 KB Output is correct
21 Correct 148 ms 11352 KB Output is correct
22 Correct 181 ms 11396 KB Output is correct
23 Correct 160 ms 11460 KB Output is correct
24 Correct 197 ms 11892 KB Output is correct
25 Correct 220 ms 15508 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 310 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 285 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -