답안 #1034784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034784	2024-07-25T18:10:43 Z	aymanrs	통행료 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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