제출 #156492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156492		rama_pang	통행료 (IOI18_highway)	C++14	100 / 100	362 ms	10776 KiB

highway

#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;
        }
    }
    ans = le;
    /* construct BFS tree */
    queue<int> q; q.push(U[ans]), q.push(V[ans]);
    color.assign(N, 0);
    color[U[ans]] = 1; color[V[ans]] = 2;
    LC.push_back(U[ans]); RC.push_back(V[ans]);

    while (!q.empty()) {
        int f = q.front(); q.pop();
        for (auto &g : G[f])  {
            int v = g.first, id = g.second;
            if (color[v] == 0) {
                if (color[f] == 1) LC.push_back(v);
                if (color[f] == 2) RC.push_back(v);
                color[v] = color[f];
                q.push(v);
            }
        }
    }
    /* binary search the answer */
    auto get = [&](vector<int> E) {
        le = 0, ri = E.size() - 1;
        while (le < ri) {
            int mid = (le + ri) / 2;
            vector<bool> cur(N);
            for (int i = mid + 1; i < E.size(); i++) {
                cur[E[i]] = true;
            }
            for (int i = 0; i < M; i++) {
                guess[i] = cur[U[i]] || cur[V[i]];
            }
            if (ask(guess) != D) {
                le = mid + 1;
            } else {
                ri = mid;
            }
        }
        return E[le];
    };
    
    answer(get(LC), get(RC));
}
 

컴파일 시 표준 에러 (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