제출 #743590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
743590		danikoynov	통행료 (IOI18_highway)	C++14	100 / 100	254 ms	18372 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;
vector < pair < int, int > > g[maxn];
int n, m;
ll a, b;
pair < int, int > ed[maxn];

vector < int > turn_active(vector < int > act)
{
    vector < int > res(m, 1);
    for (int v : act)
        res[v] = 0;
    return res;
}
vector < int > turn_inactive(vector < int > act)
{
    vector < int > res(m, 0);
    for (int v : act)
        res[v] = 1;
    return res;
}
int mark[maxn], from[maxn], dis[maxn];
int used[maxn], sp[maxn];
int sub_solve(int s, vector < int > st, ll sum, int idx)
{
    for (int i = 0; i < m; i ++)
        used[i] = 1e9, sp[i] = 0;
    for (int v : st)
        used[v] = -1;
    used[s] = 0;
    queue < int > q;
    q.push(s);
    from[s] = -1;
    vector < int > d;
    vector < int > base;
    ///exit(0);
    while(!q.empty())
    {
        int v = q.front();
        q.pop();
        d.push_back(v);
        for (pair < int, int > nb : g[v])
        {
            if (used[nb.first] == -1)
            {
                used[nb.first] = used[v] + 1;
                from[nb.first] = nb.second;
                sp[nb.second] = 1;
                base.push_back(nb.second);
                q.push(nb.first);
            }
        }
    }

    vector < int > forb;
    if (m != n - 1)
    {

    for (int i = 0; i < m; i ++)
    {
        if (i == idx)
            continue;
        if (used[ed[i].first] != 1e9 && used[ed[i].second] != 1e9 && sp[i] == 0)
            forb.push_back(i);
        else
        if (used[ed[i].first] == 1e9 && used[ed[i].second] != 1e9)
            forb.push_back(i);
        else
        if (used[ed[i].first] != 1e9 && used[ed[i].second] == 1e9)
            forb.push_back(i);
    }
    }
    int lf = 1, rf = (int)(d.size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        vector < int > cur_set;
        for (int i = max(1,mf); i < d.size(); i ++)
            cur_set.push_back(from[d[i]]);
        for (int v : forb)
            cur_set.push_back(v);
        if (ask(turn_inactive(cur_set)) != sum)
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    return d[rf];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    n = N;
    m = U.size();
    a = A;
    b = B;
    for (int i = 0; i < m; i ++)
    {
        g[U[i]].push_back({V[i], i});
        g[V[i]].push_back({U[i], i});
        ed[i] = {U[i], V[i]};
    }


    vector < int > act;
    for (int i = 0; i < m; i ++)
    act.push_back(i);

    ll base_sum = ask(turn_active(act));
    ll num_edges = base_sum / (ll)(A);
    int lf = 0, rf = m - 1;
    while(lf <= rf)
    {
        vector < int > cur;
        int mf = (lf + rf) / 2;
        for (int i = 0; i <= mf; i ++)
            cur.push_back(i);

        if (ask(turn_inactive(cur)) != num_edges * (ll)(A))
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    vector < int > ch;
    ch.push_back(lf);
    int edge = lf;
    ///cout << "here " << edge << endl;
    int v = V[edge], u = U[edge];

    queue < int > q;
    mark[v] = 1;
    mark[u] = 2;
    q.push(v);
    q.push(u);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        ///cout << cur << " : " << mark[cur] << endl;
        for (pair < int, int > nb : g[cur])
        {
            if (mark[nb.first] == 0)
            {
                mark[nb.first] = mark[cur];
                q.push(nb.first);
            }
        }
    }
    vector < int > set_s, set_t;
    for (int i = 0; i < n; i ++)
    {
        if (mark[i] == 1)
            set_s.push_back(i);
        else
            set_t.push_back(i);
    }
    int S = sub_solve(v, set_s, base_sum, edge), T = sub_solve(u, set_t, base_sum, edge);
    ///cout << S << " " << T << " : " << v << " " << u << endl;
    answer(S, T);
}

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

highway.cpp: In function 'int sub_solve(int, std::vector<int>, ll, int)':
highway.cpp:82:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int i = max(1,mf); i < d.size(); i ++)
      |                                 ~~^~~~~~~~~~

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