oj.uz

Submission #113698

# Submission time Handle Problem Language Result Execution time Memory
113698 2019-05-27T22:25:31 Z zoooma13 Highway Tolls (IOI18_highway) C++14
51 / 100
 251 ms 10628 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;

vector <pair<int ,int>> nodes;
void bfs(int s ,int p){
    nodes.clear();
    vector <int> vis(n ,0);
    vis[s] = vis[p] = 1;

    queue <pair<int,int>> nxt;
    for(auto e : adj[s])
        if(e.first == p)
            nxt.push(e);

    while(!nxt.empty()){
        int u = nxt.front().first ,f = nxt.front().second; nxt.pop();
        nodes.push_back({u,f});
        for(auto e : adj[u])
            if(!vis[e.first])
                nxt.push(e) ,vis[e.first] = 1;
    }
}

int solve(int u ,int v ,long long dist){
    bfs(u ,v);
    int st = 0 ,en = nodes.size()-1 ,mid;
    while(st < en){
        mid = (st+en+1)>>1;
        vector <int> w(n-1 ,0);
        for(int i=mid; i<=en; i++)
            w[nodes[i].second] = 1;
        if(ask(w) != dist)
            st = mid;
        else
            en = mid-1;
    }
    return nodes[st].first;
}

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

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:49: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 2424 KB Output is correct
2 Correct 5 ms 2424 KB Output is correct
3 Correct 4 ms 2344 KB Output is correct
4 Correct 4 ms 2436 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2344 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 4 ms 2424 KB Output is correct
12 Correct 4 ms 2424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2464 KB Output is correct
2 Correct 22 ms 3192 KB Output is correct
3 Correct 143 ms 9820 KB Output is correct
4 Correct 186 ms 9824 KB Output is correct
5 Correct 189 ms 10072 KB Output is correct
6 Correct 192 ms 9816 KB Output is correct
7 Correct 204 ms 9828 KB Output is correct
8 Correct 174 ms 10072 KB Output is correct
9 Correct 198 ms 9824 KB Output is correct
10 Correct 186 ms 9772 KB Output is correct
11 Correct 206 ms 8676 KB Output is correct
12 Correct 216 ms 9408 KB Output is correct
13 Correct 201 ms 9264 KB Output is correct
14 Correct 209 ms 9260 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3112 KB Output is correct
2 Correct 38 ms 3756 KB Output is correct
3 Correct 74 ms 4568 KB Output is correct
4 Correct 167 ms 8692 KB Output is correct
5 Correct 150 ms 8692 KB Output is correct
6 Correct 166 ms 9280 KB Output is correct
7 Correct 186 ms 9252 KB Output is correct
8 Correct 154 ms 8760 KB Output is correct
9 Correct 164 ms 9204 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2488 KB Output is correct
2 Correct 27 ms 3148 KB Output is correct
3 Correct 143 ms 8536 KB Output is correct
4 Correct 193 ms 9816 KB Output is correct
5 Correct 168 ms 9808 KB Output is correct
6 Correct 251 ms 9836 KB Output is correct
7 Correct 170 ms 9824 KB Output is correct
8 Correct 178 ms 9824 KB Output is correct
9 Correct 182 ms 9812 KB Output is correct
10 Correct 192 ms 9752 KB Output is correct
11 Correct 196 ms 9496 KB Output is correct
12 Correct 210 ms 9268 KB Output is correct
13 Correct 195 ms 9168 KB Output is correct
14 Correct 187 ms 8824 KB Output is correct
15 Correct 184 ms 9788 KB Output is correct
16 Correct 181 ms 9828 KB Output is correct
17 Correct 181 ms 9272 KB Output is correct
18 Correct 203 ms 9208 KB Output is correct
19 Correct 205 ms 9840 KB Output is correct
20 Correct 211 ms 9280 KB Output is correct
21 Correct 172 ms 10620 KB Output is correct
22 Correct 167 ms 10628 KB Output is correct
23 Correct 191 ms 9700 KB Output is correct
24 Correct 174 ms 9548 KB Output is correct
25 Correct 192 ms 9312 KB Output is correct

Subtask #5
0 / 18.0

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