oj.uz

Submission #113696

# Submission time Handle Problem Language Result Execution time Memory
113696 2019-05-27T20:07:38 Z zoooma13 Highway Tolls (IOI18_highway) C++14
18 / 100
 234 ms 25496 KB 
#include "highway.h"
#include "bits/stdc++.h"
using namespace std;

#define MAX_N 90004

int qs = 0;
long long Ask(vector <int> w){
    assert(++qs <= 60);
    //cout << qs << endl;
    return ask(w);
}

int n;
vector <pair <int ,int>> adj[MAX_N];
vector <pair <int ,int>> edges;

int depth[MAX_N];
vector <int> atdep[MAX_N];
void dfs(int u ,int p ,int d=1){
    depth[u] = d;
    for(auto v : adj[u]) if(v.first != p){
        atdep[d].push_back(v.second);
        dfs(v.first ,u ,d+1);
    }
}

int known_depth = -1;
int solve(int u ,int v ,long long dist){
    memset(depth ,0 ,sizeof depth);
    for(int i=0; i<MAX_N; i++)
        atdep[i].clear();

    dfs(u ,v);

   if(!~known_depth){
        int st = 1 ,en = (*max_element(depth ,depth+n))-1 ,mid;
        while(st <= en){
            mid = (st+en)>>1;
            vector <int> w(n-1 ,0);
            for(int i : atdep[mid])
                w[i] = 1;
            if(Ask(w) != dist)
                st = mid+1;
            else
                en = mid-1;
        }
        known_depth = st-1;
    }

    vector <int>&eds = atdep[known_depth];
    int st = 0 ,en = eds.size()-1 ,mid;
    while(st < en){
        mid = (st+en)>>1;
        vector <int> w(n-1 ,0);
        for(int i=st; i<=mid; i++)
            w[eds[i]] = 1;
        if(Ask(w) != dist)
            en = mid;
        else
            st = mid+1;
    }

    if(en == -1)
        return u;
    u = edges[eds[en]].first ,v = edges[eds[en]].second;
    return depth[u] > depth[v] ? u : v;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N;
    assert(U.size() == N-1);
    for(int i=0; i<N-1; i++)
        adj[U[i]].push_back({V[i] ,i}),
        adj[V[i]].push_back({U[i] ,i}),
        edges.push_back({U[i] ,V[i]});

    long long dist = Ask(vector<int>(n-1 ,0));
    int st = 0 ,en = n-1 ,mid;
    while(st < en){
        mid = (st+en)>>1;
        vector <int> w(n-1 ,0);
        for(int i=st; i<=mid; i++)
            w[i] = 1;
        if(Ask(w) != dist)
            en = mid;
        else
            st = mid+1;
    }

    int s = solve(U[en] ,V[en] ,dist);
    known_depth = (dist/A)-known_depth-1;
    int t = solve(V[en] ,U[en] ,dist);
    answer(s ,t);
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from highway.cpp:2:
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(U.size() == N-1);
            ~~~~~~~~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4904 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 6 ms 4860 KB Output is correct
4 Correct 6 ms 4860 KB Output is correct
5 Correct 7 ms 4856 KB Output is correct
6 Correct 6 ms 4856 KB Output is correct
7 Correct 6 ms 4816 KB Output is correct
8 Correct 6 ms 4904 KB Output is correct
9 Correct 6 ms 4856 KB Output is correct
10 Correct 6 ms 4808 KB Output is correct
11 Correct 7 ms 4776 KB Output is correct
12 Correct 6 ms 4856 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4856 KB Output is correct
2 Correct 21 ms 5772 KB Output is correct
3 Correct 181 ms 11800 KB Output is correct
4 Correct 199 ms 11752 KB Output is correct
5 Correct 200 ms 11748 KB Output is correct
6 Correct 202 ms 11708 KB Output is correct
7 Correct 179 ms 11780 KB Output is correct
8 Correct 183 ms 11716 KB Output is correct
9 Correct 173 ms 11784 KB Output is correct
10 Correct 175 ms 11716 KB Output is correct
11 Correct 216 ms 12892 KB Output is correct
12 Correct 221 ms 14180 KB Output is correct
13 Correct 176 ms 13536 KB Output is correct
14 Correct 211 ms 13656 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6520 KB Output is correct
2 Correct 45 ms 7996 KB Output is correct
3 Correct 81 ms 10040 KB Output is correct
4 Correct 141 ms 16712 KB Output is correct
5 Correct 127 ms 16808 KB Output is correct
6 Correct 167 ms 18840 KB Output is correct
7 Correct 173 ms 21220 KB Output is correct
8 Correct 175 ms 17772 KB Output is correct
9 Correct 174 ms 18932 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 27 ms 5544 KB Output is correct
3 Correct 136 ms 10080 KB Output is correct
4 Correct 195 ms 11624 KB Output is correct
5 Correct 189 ms 11764 KB Output is correct
6 Correct 181 ms 11656 KB Output is correct
7 Correct 191 ms 11840 KB Output is correct
8 Correct 181 ms 11632 KB Output is correct
9 Correct 204 ms 11788 KB Output is correct
10 Correct 192 ms 11756 KB Output is correct
11 Correct 175 ms 13120 KB Output is correct
12 Correct 225 ms 14380 KB Output is correct
13 Correct 231 ms 13796 KB Output is correct
14 Correct 197 ms 13612 KB Output is correct
15 Correct 187 ms 11748 KB Output is correct
16 Correct 185 ms 11012 KB Output is correct
17 Correct 205 ms 13152 KB Output is correct
18 Correct 202 ms 13864 KB Output is correct
19 Correct 189 ms 11656 KB Output is correct
20 Correct 234 ms 14752 KB Output is correct
21 Correct 144 ms 11872 KB Output is correct
22 Correct 192 ms 11876 KB Output is correct
23 Correct 209 ms 12208 KB Output is correct
24 Runtime error 202 ms 25496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 9464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 9336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -