제출 #1014988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014988		ThegeekKnight16	통행료 (IOI18_highway)	C++17	90 / 100	167 ms	10852 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
vector<vector<pair<int, int>>> grafo;
vector<int> Marc;

// long long ask(vector<int> w);

int findNode(int S, vector<int> &w, int matters, ll dist)
{
    queue<int> q; vector<int> poss;
    Marc[S] = 1; q.push(S);
    // w[matters] = 1;
    while (!q.empty())
    {
        int cur = q.front(); q.pop();
        poss.push_back(cur);

        for (auto [viz, id] : grafo[cur])
        {
            if (Marc[viz] || w[id]) continue;
            Marc[viz] = 1; q.push(viz);
        }
    }
    // w[matters] = 0;

    int id = 0;
    for (int k = 16; k >= 0; k--)
    {
        int m = id | (1 << k);
        if (m >= poss.size()) continue;
        for (int v = 0; v < min(m, (int)poss.size()); v++)
            for (auto [viz, id] : grafo[poss[v]])
                w[id] = 0;

        for (int v = m; v < poss.size(); v++)
            for (auto [viz, id] : grafo[poss[v]])
                w[id] = 1;

        for (int i = matters+1; i < w.size(); i++) w[i] = 1;
        if (ask(w) != dist) id |= (1 << k);
    }

    return poss[id];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    int M = U.size();
    vector<int> w(M, 0);
    ll dist = ask(w);

    int matters = 0;
    for (int k = 16; k >= 0; k--)
    {
        int m = matters | (1 << k);
        if (m >= M) continue;
        for (int i = 0; i < min(m, M); i++) w[i] = 0;
        for (int i = m; i < M; i++) w[i] = 1;
        if (ask(w) != dist) matters |= (1 << k);
    }

    for (int i = 0; i <= matters; i++) w[i] = 0;
    for (int i = matters+1; i < M; i++) w[i] = 1;

    grafo.resize(N); Marc.resize(N, 0);
    for (int i = 0; i < M; i++)
    {
        grafo[U[i]].emplace_back(V[i], i);
        grafo[V[i]].emplace_back(U[i], i);
    }
    // cerr << "matters: " << matters << ", (" << U[matters] << ", " << V[matters] << ") " << '\n';
    int S = findNode(U[matters], w, matters, dist);

    fill(Marc.begin(), Marc.end(), 0);
    for (int i = 0; i <= matters; i++) w[i] = 0;
    for (int i = matters+1; i < M; i++) w[i] = 1;

    int T = findNode(S, w, matters, dist);
    // cerr << "S: " << S << ", T: " << T << '\n';
    answer(S, T);
}

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

highway.cpp: In function 'int findNode(int, std::vector<int>&, int, ll)':
highway.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if (m >= poss.size()) continue;
      |             ~~^~~~~~~~~~~~~~
highway.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int v = m; v < poss.size(); v++)
      |                         ~~^~~~~~~~~~~~~
highway.cpp:41:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = matters+1; i < w.size(); i++) w[i] = 1;
      |                                 ~~^~~~~~~~~~

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