Submission #156492

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
156492	2019-10-06 08:18:46	rama_pang	Highway Tolls (IOI18_highway)	C++14	100 / 100	362 ms	10776 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>
using namespace std;
using lint = long long;
 
lint N, M, A, B;
vector<vector<pair<int, int>>> G;
vector<int> LC, RC, color;
int S, T;
void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) {
    N = _N, A = _A, B = _B, M = U.size(); G.resize(N);
    for (int i = 0; i < M; i++) {
        G[U[i]].emplace_back(V[i], i);
        G[V[i]].emplace_back(U[i], i);
    }
    vector<int> guess(M, 0);
    lint D = ask(guess);
    lint le, ri, ans, check;
    /* find and edge e = uv, then construct tree rooted from u and from v */
    le = 0, ri = M - 1;
    while (le < ri) {
        lint mid = (le + ri) / 2;
        for (int i = 0; i < M; i++) guess[i] = i <= mid;
        if (ask(guess) != D) {
            ri = mid;                
        } else {
            le = mid + 1;
        }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:41:30: warning: unused variable 'id' [-Wunused-variable]
             int v = g.first, id = g.second;
                              ^~
highway.cpp: In lambda function:
highway.cpp:56:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = mid + 1; i < E.size(); i++) {
                                   ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:19:23: warning: unused variable 'check' [-Wunused-variable]
     lint le, ri, ans, check;
                       ^~~~~

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