oj.uz

Submission #113660

# Submission time Handle Problem Language Result Execution time Memory
113660 2019-05-27T14:18:13 Z zoooma13 Highway Tolls (IOI18_highway) C++14
18 / 100
 222 ms 20876 KB 
#include "highway.h"
#include "bits/stdc++.h"
using namespace std;

#define MAX_N 90004

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 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);

    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;
    }

    vector <int>&eds = atdep[--st];
    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);
    int t = solve(V[en] ,U[en] ,dist);

    answer(s ,t);
}

Compilation message

highway.cpp: In function 'int solve(int, int, long long int)':
highway.cpp:41:35: warning: right operand of comma operator has no effect [-Wunused-value]
     st = 0 ,en = eds.size()-1 ,mid;
                                   ^
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:61: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 4 ms 4984 KB Output is correct
2 Correct 6 ms 4820 KB Output is correct
3 Correct 7 ms 4900 KB Output is correct
4 Correct 7 ms 4832 KB Output is correct
5 Correct 7 ms 4856 KB Output is correct
6 Correct 7 ms 4892 KB Output is correct
7 Correct 7 ms 4788 KB Output is correct
8 Correct 7 ms 4984 KB Output is correct
9 Correct 6 ms 4900 KB Output is correct
10 Correct 6 ms 4856 KB Output is correct
11 Correct 7 ms 4824 KB Output is correct
12 Correct 7 ms 4812 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 26 ms 5544 KB Output is correct
3 Correct 200 ms 11332 KB Output is correct
4 Correct 179 ms 11384 KB Output is correct
5 Correct 137 ms 11408 KB Output is correct
6 Correct 156 ms 11296 KB Output is correct
7 Correct 156 ms 11424 KB Output is correct
8 Correct 177 ms 11368 KB Output is correct
9 Correct 182 ms 11304 KB Output is correct
10 Correct 190 ms 11412 KB Output is correct
11 Correct 202 ms 12540 KB Output is correct
12 Correct 200 ms 14048 KB Output is correct
13 Correct 206 ms 13144 KB Output is correct
14 Correct 197 ms 13188 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6568 KB Output is correct
2 Correct 46 ms 8048 KB Output is correct
3 Correct 65 ms 9884 KB Output is correct
4 Correct 173 ms 17128 KB Output is correct
5 Correct 133 ms 17260 KB Output is correct
6 Correct 174 ms 19120 KB Output is correct
7 Correct 180 ms 20876 KB Output is correct
8 Correct 178 ms 18140 KB Output is correct
9 Correct 137 ms 18672 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4868 KB Output is correct
2 Correct 27 ms 5496 KB Output is correct
3 Correct 149 ms 9880 KB Output is correct
4 Correct 217 ms 11284 KB Output is correct
5 Correct 205 ms 11300 KB Output is correct
6 Correct 176 ms 11284 KB Output is correct
7 Correct 183 ms 11308 KB Output is correct
8 Correct 184 ms 11296 KB Output is correct
9 Correct 179 ms 11308 KB Output is correct
10 Correct 183 ms 11320 KB Output is correct
11 Correct 222 ms 12760 KB Output is correct
12 Correct 209 ms 13916 KB Output is correct
13 Correct 188 ms 13400 KB Output is correct
14 Correct 186 ms 13172 KB Output is correct
15 Correct 174 ms 11268 KB Output is correct
16 Correct 178 ms 11172 KB Output is correct
17 Correct 200 ms 12932 KB Output is correct
18 Correct 208 ms 13616 KB Output is correct
19 Correct 183 ms 11308 KB Output is correct
20 Correct 204 ms 14396 KB Output is correct
21 Correct 181 ms 11524 KB Output is correct
22 Correct 145 ms 11532 KB Output is correct
23 Incorrect 195 ms 11892 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 9384 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 9360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -