oj.uz

Submission #113701

# Submission time Handle Problem Language Result Execution time Memory
113701 2019-05-28T00:09:55 Z zoooma13 Highway Tolls (IOI18_highway) C++14
0 / 100
 248 ms 13324 KB 
#include "highway.h"
#include "bits/stdc++.h"
using namespace std;

#define MAX_N 90004

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

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(m ,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;
}

vector <pair<int ,int>> t_adj[MAX_N];
void get_bfs_tree(int s){
    vector <bool> vis(n);
    queue <int> nxt; nxt.push(s);
    while(!nxt.empty()){
        int u = nxt.front(); nxt.pop();
        for(auto e : adj[u])
            if(!vis[e.first]){
                vis[e.first] = 1;
                t_adj[u].push_back(e);
                nxt.push(e.first);
            }
    }
}

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

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

    get_bfs_tree(U[en]);
    for(int i=0; i<n; i++)
        swap(adj[i] ,t_adj[i]);

    int s = solve(U[en] ,V[en] ,dist);
    int t = solve(V[en] ,U[en] ,dist);
    answer(s ,t);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4600 KB Output is correct
2 Correct 26 ms 5496 KB Output is correct
3 Correct 207 ms 12892 KB Output is correct
4 Incorrect 192 ms 12888 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 5544 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 Correct 7 ms 4600 KB Output is correct
2 Incorrect 27 ms 5388 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5392 KB Output is correct
2 Correct 30 ms 5556 KB Output is correct
3 Correct 232 ms 13196 KB Output is correct
4 Incorrect 242 ms 12460 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5372 KB Output is correct
2 Correct 25 ms 5580 KB Output is correct
3 Correct 244 ms 12700 KB Output is correct
4 Incorrect 248 ms 13324 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -