제출 #594327

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
594327	2022-07-12 10:59:52	Soumya1	통행료 (IOI18_highway)	C++17	100 / 100	248 ms	11764 KiB

highway

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "highway.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
const int mxN = 9e4 + 5;
vector<pair<int, int>> ad[mxN];
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
  int m = U.size();
  for (int i = 0; i < m; i++) {
    ad[U[i]].push_back({i, V[i]});
    ad[V[i]].push_back({i, U[i]});
  }
  int lo = 0, hi = m - 1;
  int len = ask(vector<int> (m)) / A;
  while (lo < hi) {
    int mid = (lo + hi) >> 1;
    vector<int> v(U.size(), 1);
    for (int i = 0; i <= mid; i++) {
      v[i] = 0;
    }
    if (ask(v) == 1LL * A * len) hi = mid;
    else lo = mid + 1;
  }
  int s = U[lo], e = V[lo];
  vector<int> d(n, -1), root(n);
  root[s] = s, root[e] = e;
  queue<int> q;
  vector<int> S, E, par(n);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In lambda function:
highway.cpp:60:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |       for (int i = 0; i < ee.size(); i++) v[par[ee[i]]] = 0;
      |                       ~~^~~~~~~~~~~

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