제출 #292082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292082		SamAnd	통행료 (IOI18_highway)	C++17	12 / 100	305 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;

int n, m;
vector<int> g[N];
vector<int> gi[N];

int d[N];
int u[N];
void dfs0(int x, int p)
{
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
        {
            u[x] = gi[x][i];
            continue;
        }
        d[h] = d[x] + 1;
        dfs0(h, x);
    }
}

void find_pair(int N_, std::vector<int> U, std::vector<int> V, int A, int B)
{
    n = N_;
    m = sz(U);
    for (int i = 0; i < m; ++i)
    {
        int x = U[i];
        int y = V[i];
        g[x].push_back(y);
        g[y].push_back(x);
        gi[x].push_back(i);
        gi[y].push_back(i);
    }

    vector<int> v;
    v.assign(m, 0);
    int dd = ask(v) / A;

    dfs0(0, 0);
    vector<int> t;
    for (int x = 0; x < n; ++x)
    {
        if (d[x] == dd)
        {
            t.push_back(x);
        }
    }
    int l = 0, r = sz(t) - 1;
    int ans;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        v.assign(m, 0);
        for (int i = 0; i <= mid; ++i)
        {
            v[u[t[i]]] = 1;
        }
        if (ask(v) != dd * 1LL * A)
        {
            ans = t[mid];
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    answer(0, ans);
}

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

highway.cpp: In function 'void dfs0(int, int)':
highway.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:78:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |     answer(0, ans);
      |     ~~~~~~^~~~~~~~

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