Submission #1034784

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1034784	2024-07-25T18:10:43 Z	aymanrs	Highway Tolls (IOI18_highway)	C++14	18 / 100	304 ms	262144 KB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
  int p;
  vector<pair<node*, int>> l;
  int d;
};
void dfs(node* n, node* p, int d){
  n->d = d;
  for(auto [c,x] : n->l){
    if(c==p) continue;
    c->p = x;
    dfs(c, n, d+1);
  }
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  node g[N];
  int m = U.size();
  bool tsub = true;
  for(int i = 0;i < U.size();i++){
    tsub &= U[i]==i && V[i]==i+1;
    g[U[i]].l.emplace_back(&g[V[i]], i);
    g[V[i]].l.emplace_back(&g[U[i]], i);
  }
  vector<int> w(m, 0);
  long long dis = ask(w)/A;
  if(tsub){
    int l = 0, r = N-1, mid;
    while(l<r){
      mid = l+r+1>>1;
      for(int i = l;i < mid;i++) w[i]=1;
      long long re = ask(w);
      for(int i = l;i < mid;i++) w[i]=0;
      if(re > dis*A) r=mid-1;
      else l = mid;
    }
    answer(l,l+dis);
    return;
  }
  dfs(&g[0], NULL, 0);
  vector<pair<int, int>> v;
  for(int i = 1;i < N;i++) if(g[i].d == dis) v.emplace_back(g[i].p, i);
  int l = 0, r = v.size()-1, mid;
  while(l<r){
    mid = l+r>>1;
    for(int i = l;i <= mid;i++) w[v[i].first] = 1;
    long long re = ask(w);
    for(int i = l;i <= mid;i++) w[v[i].first] = 0;
    if(re > dis*A){
      r = mid;
    } else l = mid+1;
  }
  answer(0, v[l].second);
}

Compilation message

highway.cpp: In function 'void dfs(node*, node*, int)':
highway.cpp:11:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   11 |   for(auto [c,x] : n->l){
      |            ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i = 0;i < U.size();i++){
      |                 ~~^~~~~~~~~~
highway.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |       mid = l+r+1>>1;
      |             ~~~^~
highway.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     mid = l+r>>1;
      |           ~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	7 ms	1536 KB	Output is correct
3	Correct	81 ms	10332 KB	Output is correct
4	Correct	68 ms	10336 KB	Output is correct
5	Correct	75 ms	10320 KB	Output is correct
6	Correct	81 ms	10356 KB	Output is correct
7	Correct	69 ms	10448 KB	Output is correct
8	Correct	69 ms	10556 KB	Output is correct
9	Correct	65 ms	10356 KB	Output is correct
10	Correct	67 ms	10552 KB	Output is correct
11	Correct	68 ms	11088 KB	Output is correct
12	Correct	70 ms	11104 KB	Output is correct
13	Correct	65 ms	11056 KB	Output is correct
14	Correct	71 ms	10808 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1368 KB	Output is correct
2	Correct	13 ms	2392 KB	Output is correct
3	Correct	22 ms	3472 KB	Output is correct
4	Correct	60 ms	9808 KB	Output is correct
5	Correct	57 ms	9808 KB	Output is correct
6	Correct	68 ms	9932 KB	Output is correct
7	Correct	62 ms	9840 KB	Output is correct
8	Correct	62 ms	9812 KB	Output is correct
9	Correct	55 ms	9808 KB	Output is correct