oj.uz

Submission #263247

# Submission time Handle Problem Language Result Execution time Memory
263247 2020-08-13T14:37:25 Z UserIsUndefined Highway Tolls (IOI18_highway) C++14
12 / 100
 130 ms 8580 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

int depth ;

vector<pair<int,int>> adj[90005];
vector<int> can;
int depthh[90005];

void dfs(int v , int dep, int p, int idx){
//    cout << v << " " << dep << " " << p << " " << idx << " here "<<  endl;
    depthh[v] = dep;
    if (dep == depth){
        can.push_back(idx);
        return;
    }



    for (pair<int,int> e : adj[v]){
        if (e.first != p){
            dfs(e.first, dep + 1 , v, e.second);
        }
    }

}


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

    vector<int> ans;

    vector<int> test(m , 0);



    long long li = ask(test);

    depth = li/A;

//    cout << "dipth" << depth << endl;


    for (int i = 0 ; i < m ; i++){
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }



    dfs(0, 0 , -1, -1);



//    for (int cand : can){
////        cout << "This is cand" << cand << endl;
//    }


    int low = 0;
    int high = can.size() - 1;

    while(low < high){

        int mid = (low + high)/2;
//         cout << low  << " h " << high << endl;
        vector<int> call(m);

        for (int i = low ; i <= mid ; i++){
            call[can[i]] = 1;
        }

        long long an = ask(call);

        if (an - B + A == li){
            high = mid;
        }
        else {
            low = mid + 1;
        }




    }

    if (low > high)low--;
    int ed = can[low];

    int s = -1;

    if (depthh[U[ed]] == depth){
        s = U[ed];
    }
    else {
        s = V[ed];
    }





    answer(0 , s);


}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2432 KB Output is correct
2 Correct 12 ms 3072 KB Output is correct
3 Correct 119 ms 8452 KB Output is correct
4 Correct 117 ms 8536 KB Output is correct
5 Correct 123 ms 8440 KB Output is correct
6 Correct 106 ms 8340 KB Output is correct
7 Correct 116 ms 8332 KB Output is correct
8 Correct 130 ms 8452 KB Output is correct
9 Correct 107 ms 8468 KB Output is correct
10 Correct 122 ms 8580 KB Output is correct
11 Correct 106 ms 8056 KB Output is correct
12 Correct 117 ms 8472 KB Output is correct
13 Correct 119 ms 8312 KB Output is correct
14 Correct 110 ms 8568 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2944 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2560 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3740 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 3200 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -