제출 #156470

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

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e8;
const lint MAXN = 150005;
 
lint N, M, A, B;
vector<int> G[MAXN];
lint dist[MAXN];
int S, T;
struct edge {
    int u, v, id;
    edge(int uu, int vv, int idd): u(uu), v(vv), id(idd) { }
    bool operator < (const edge &o) {
        return dist[v] < dist[o.v] || (dist[v] == dist[o.v] && v < o.v) || (v == o.v && u < o.u);
    }
};
 
vector<edge> E;
 
void bfs(int n) {
    queue<int> q;
    int step = 0;
    q.push(n);
    for (; q.size(); step++) {
        int sz = q.size();
        while (sz--) {
            int f = q.front();
            q.pop();
            if (dist[f] != INF) continue;
            dist[f] = step;
            for (auto &g : G[f])  {
                if (dist[g] == INF) q.push(g);
            }
        }
    }
}
 
void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) {
    N = _N, A = _A, B = _B, M = U.size();
    for (int i = 0; i < M; i++) {
        G[U[i]].emplace_back(V[i]);
        G[V[i]].emplace_back(U[i]);
        E.emplace_back(U[i], V[i], i);
    }
    vector<int> guess(M, 0);
    lint D = ask(guess) / A;
    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;
        guess.assign(M, 0);
        for (int i = 0; i <= mid; i++) guess[i] = 1;
        check = ask(guess);
        if (check > D * A) {
            ans = mid;
            ri = mid - 1;                
        } else {
            le = mid + 1;
        }
    }
    int root = E[ans].u;
    int root2 = E[ans].v;
    /* binary search from to find the opther pair */
    for (int i = 0; i < N; i++) dist[i] = INF;
    bfs(root);
    for (int i = 0; i < M; i++) {
        if (dist[E[i].u] > dist[E[i].v]) swap(E[i].u, E[i].v);
    }
    sort(E.begin(), E.end());
    le = 0, ri = M - 1;
    ans = (dist[E.back().u] > dist[E.back().v])? E.back().u : E.back().v;
    while (le <= ri) {
        guess.assign(M, 1); //how to find path when there are many paths?
        lint mid = (le + ri) / 2; //we can just set all edges to heavy
        for (int i = 0; i <= mid; i++) guess[E[i].id] = 0; //and binary search by setting 0...mid to light
        check = ask(guess); //then the other edges become obsolete, and we can get the endpoint of the shortest path easily
        if (check == D * A) {
            ans = mid;
            ri = mid - 1;
        } else {
            // ans = mid;
            le = mid + 1;
        }
    }
    S = E[ans].v;
    /* found one pair, now find the other one */
 
    for (int i = 0; i < N; i++) dist[i] = INF;
    bfs(S);
    for (int i = 0; i < M; i++) {
        if (dist[E[i].u] > dist[E[i].v]) swap(E[i].u, E[i].v);
    }
    sort(E.begin(), E.end());
    le = 0, ri = M - 1;
    for (int i = 0; i < M; i++) {
        if (dist[E[i].u] < min(dist[root], dist[root2])) continue;
        le = i;
        break;
    }
    for (int i = M - 1; i >= 0; i--) {
        if (dist[E[i].u] > D) continue;
        ri = i;
        break;
    }
    ans = (dist[E.back().u] > dist[E.back().v])? E.back().u : E.back().v;
    while (le <= ri) { //then we can do the same thing to find T from root S, by the same logic
        guess.assign(M, 1);
        lint mid = (le + ri) / 2;
        for (int i = 0; i <= mid; i++) guess[E[i].id] = 0;
        check = ask(guess);
        if (check == D * A) {
            ans = mid;
            ri = mid - 1;
        } else {
            // ans = mid;
            le = mid + 1;
        }
    }
    ans = E[ans].v;
    T = ans;
    /* found one pair, now find the other one */
    
    // cout << S  << " " << T << "\n";
    answer(S, T);
}
 
/*
 
4 4 1 3 1 0
0 1
0 2
0 3
1 2
 
4 3 1 3 0 1
0 1
0 2
0 3
 
4 3 1 3 2 3
0 1
0 3
1 2
 
 
*/

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

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:64:21: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int root = E[ans].u;
                     ^

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