Submission #611775

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
611775	2022-07-29T07:23:53 Z	Jomnoi	Highway Tolls (IOI18_highway)	C++17	18 / 100	155 ms	15636 KB

highway

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

// subtask 1, 2

const int MAX_N = 9e4 + 5;

int S, T;
long long result;
vector <int> U, V, W;
vector <int> graph[MAX_N];
vector <int> canbeanswer;
int holdedge[MAX_N];

void dfs(int u, int p, int depth) {
    if(depth == 0) {
        canbeanswer.push_back(u);
        return;
    }
    for(auto i : graph[u]) {
        int v = u ^ U[i] ^ V[i];
        if(v != p) {
            holdedge[v] = i;
            dfs(v, u, depth - 1);
        }
    }
}

void dfs2(int u, int p) {
    canbeanswer.push_back(u);
    for(auto i : graph[u]) {
        int v = u ^ U[i] ^ V[i];
        if(v != p) {
            holdedge[v] = i;
            dfs2(v, u);
        }
    }
}

void find_pair(int N, vector <int> u, vector <int> v, int A, int B) {
    int M = u.size();
    U.resize(M);
    V.resize(M);
    W.resize(M, 0);
    bool sub3 = true;
    for(int i = 0; i < M; i++) {
        U[i] = u[i], V[i] = v[i];
        graph[U[i]].push_back(i);
        graph[V[i]].push_back(i);

        if(U[i] != i or V[i] != i + 1) {
            sub3 = false;
        }
    }
    
    if(sub3 == true) {
        int rt;
        for(int i = 0; i < N; i++) {
            if(graph[i].size() == 1) {
                rt = i;
                break;
            }
        }

        dfs2(rt, -1);

        W.clear();
        W.resize(M, 1);
        long long need = ask(W);

        int l = 1, r = N - 1;
        while(l <= r) {
            int mid = (l + r) / 2;

            W.clear();
            W.resize(M, 0);
            for(int i = 1; i <= mid; i++) {
                W[holdedge[canbeanswer[i]]] = 1;
            }

            result = ask(W);
            if(result < need) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
                S = mid;
            }
        }

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

            W.clear();
            W.resize(M, 0);
            for(int i = mid + 1; i <= S; i++) {
                W[holdedge[canbeanswer[i]]] = 1;
            }

            result = ask(W);
            if(result < need) {
                r = mid - 1;
            }
            else {
                l = mid + 1;
                T = mid;
            }
        }
        answer(canbeanswer[S], canbeanswer[T]);
    }
    else { // sub12
        S = 0;
        result = ask(W);

        int numberofEdge = result / A;

        dfs(0, -1, numberofEdge);

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

            W.clear();
            W.resize(M, 0);
            for(int i = 0; i <= mid; i++) {
                W[holdedge[canbeanswer[i]]] = 1;
            }

            result = ask(W);
            if(result == 1ll*numberofEdge * A) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
                T = mid;
            }
        }
        answer(S, canbeanswer[T]);
    }
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:66:13: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |         dfs2(rt, -1);
      |         ~~~~^~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2384 KB	Output is correct
2	Correct	1 ms	2384 KB	Output is correct
3	Correct	1 ms	2384 KB	Output is correct
4	Correct	2 ms	2384 KB	Output is correct
5	Correct	2 ms	2384 KB	Output is correct
6	Correct	1 ms	2384 KB	Output is correct
7	Correct	2 ms	2384 KB	Output is correct
8	Correct	1 ms	2384 KB	Output is correct
9	Correct	1 ms	2384 KB	Output is correct
10	Correct	2 ms	2384 KB	Output is correct
11	Correct	1 ms	2384 KB	Output is correct
12	Correct	1 ms	2384 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2384 KB	Output is correct
2	Correct	10 ms	3024 KB	Output is correct
3	Correct	130 ms	8272 KB	Output is correct
4	Correct	97 ms	8292 KB	Output is correct
5	Correct	87 ms	8248 KB	Output is correct
6	Correct	95 ms	8184 KB	Output is correct
7	Correct	142 ms	8216 KB	Output is correct
8	Correct	97 ms	8268 KB	Output is correct
9	Correct	82 ms	8168 KB	Output is correct
10	Correct	104 ms	8356 KB	Output is correct
11	Correct	106 ms	8288 KB	Output is correct
12	Correct	93 ms	8872 KB	Output is correct
13	Correct	114 ms	8752 KB	Output is correct
14	Correct	88 ms	9000 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3900 KB	Output is correct
2	Correct	20 ms	5384 KB	Output is correct
3	Correct	35 ms	6872 KB	Output is correct
4	Correct	85 ms	15636 KB	Output is correct
5	Correct	155 ms	15568 KB	Output is correct
6	Correct	127 ms	15584 KB	Output is correct
7	Correct	87 ms	15576 KB	Output is correct
8	Correct	121 ms	15576 KB	Output is correct
9	Correct	140 ms	15576 KB	Output is correct