Submission #291045

#	Time	Username	Problem	Language	Result	Execution time	Memory
291045		evpipis	Highway Tolls (IOI18_highway)	C++11	100 / 100	521 ms	14616 KiB

highway

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;

const int len = 2e5+5;
ii edge[len];
int n, m, vis[len];
ll dis;
vector<ii> adj[len];

void find_bridge(int &x, int &y){
    int l = 0, r = m-1, ans;
    while (l <= r){
        int mid = (l+r)/2;

        vector<int> temp(m, 0);
        for (int j = 0; j <= mid; j++)
            temp[j] = 1;

        if (ask(temp) > dis)
            r = mid-1, ans = mid;
        else
            l = mid+1;
    }

    x = edge[ans].fi;
    y = edge[ans].se;
}

void build_tree(int x, int y, vector<int> &order_x, vector<int> &order_y){
    queue<int> myq;
    vis[x] = 1, vis[y] = 2;
    myq.push(x), myq.push(y);

    while (!myq.empty()){
        int u = myq.front();
        myq.pop();

        if (vis[u] == 1)
            order_x.pb(u);
        else
            order_y.pb(u);

        for (auto v: adj[u]){
            if (vis[v.fi]) continue;

            vis[v.fi] = vis[u];
            myq.push(v.fi);
        }
    }

    reverse(order_x.begin(), order_x.end());
    reverse(order_y.begin(), order_y.end());
}

void find_ans(vector<int> order_x, vector<int> order_y, int &x, int &y){
    int l = 0, r = order_x.size()-1, ans;
    while (l <= r){
        int mid = (l+r)/2;

        vector<int> temp(m, 0);
        for (int j = 0; j <= mid; j++)
            for (auto v: adj[order_x[j]])
                temp[v.se] = 1;

        if (ask(temp) > dis)
            r = mid-1, ans = mid;
        else
            l = mid+1;
    }

    x = order_x[ans];

    l = 0, r = order_y.size()-1;
    while (l <= r){
        int mid = (l+r)/2;

        vector<int> temp(m, 0);
        for (int j = 0; j <= mid; j++)
            for (auto v: adj[order_y[j]])
                temp[v.se] = 1;

        if (ask(temp) > dis)
            r = mid-1, ans = mid;
        else
            l = mid+1;
    }

    y = order_y[ans];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    n = N, m = U.size();

    for (int i = 0; i < m; i++){
        int u = U[i]+1, v = V[i]+1;
        edge[i] = mp(u, v);
        adj[u].pb(mp(v, i));
        adj[v].pb(mp(u, i));
    }

    dis = ask(vector<int>(m, 0));

    int x, y;
    find_bridge(x, y);

    //printf("bridge: x = %d, y = %d\n", x, y);

    vector<int> order_x, order_y;
    build_tree(x, y, order_x, order_y);

    int st, en;
    find_ans(order_x, order_y, st, en);
    //printf("st = %d, en = %d\n", st, en);

    answer(st-1, en-1);
}
/*
4 4 1 3 1 3
0 1
0 2
0 3
1 2
*/

Compilation message (stderr)

highway.cpp: In function 'void find_bridge(int&, int&)':
highway.cpp:6:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
    6 | #define se second
      |            ^~~~~~
highway.cpp:19:25: note: 'ans' was declared here
   19 |     int l = 0, r = m-1, ans;
      |                         ^~~
highway.cpp: In function 'void find_ans(std::vector<int>, std::vector<int>, int&, int&)':
highway.cpp:79:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |     x = order_x[ans];
      |                    ^

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