oj.uz

Submission #113659

# Submission time Handle Problem Language Result Execution time Memory
113659 2019-05-27T14:14:33 Z zoooma13 Highway Tolls (IOI18_highway) C++14
5 / 100
 212 ms 21468 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 ,int 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]});

    int 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, 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 7 ms 4812 KB Output is correct
2 Correct 6 ms 4812 KB Output is correct
3 Correct 6 ms 4856 KB Output is correct
4 Correct 6 ms 4812 KB Output is correct
5 Correct 6 ms 4896 KB Output is correct
6 Correct 6 ms 4808 KB Output is correct
7 Correct 7 ms 4856 KB Output is correct
8 Correct 6 ms 4808 KB Output is correct
9 Correct 6 ms 4808 KB Output is correct
10 Correct 6 ms 4856 KB Output is correct
11 Correct 6 ms 4900 KB Output is correct
12 Correct 6 ms 4884 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4948 KB Output is correct
2 Correct 47 ms 5604 KB Output is correct
3 Correct 182 ms 11320 KB Output is correct
4 Correct 205 ms 11396 KB Output is correct
5 Correct 196 ms 11400 KB Output is correct
6 Correct 191 ms 11408 KB Output is correct
7 Correct 186 ms 11440 KB Output is correct
8 Correct 194 ms 11396 KB Output is correct
9 Correct 190 ms 11320 KB Output is correct
10 Correct 187 ms 11404 KB Output is correct
11 Correct 198 ms 12568 KB Output is correct
12 Correct 212 ms 13828 KB Output is correct
13 Correct 197 ms 13124 KB Output is correct
14 Incorrect 182 ms 13192 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6520 KB Output is correct
2 Correct 46 ms 8080 KB Output is correct
3 Correct 59 ms 9888 KB Output is correct
4 Correct 169 ms 17144 KB Output is correct
5 Correct 164 ms 17220 KB Output is correct
6 Correct 176 ms 19108 KB Output is correct
7 Correct 179 ms 20860 KB Output is correct
8 Correct 170 ms 18016 KB Output is correct
9 Incorrect 175 ms 21468 KB Output is incorrect: {s, t} is wrong.

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4952 KB Output is correct
2 Correct 27 ms 5572 KB Output is correct
3 Correct 149 ms 9872 KB Output is correct
4 Correct 197 ms 11232 KB Output is correct
5 Correct 186 ms 11320 KB Output is correct
6 Correct 192 ms 11288 KB Output is correct
7 Correct 193 ms 11304 KB Output is correct
8 Correct 190 ms 11348 KB Output is correct
9 Incorrect 200 ms 11324 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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