oj.uz

Submission #113664

# Submission time Handle Problem Language Result Execution time Memory
113664 2019-05-27T15:25:44 Z zoooma13 Highway Tolls (IOI18_highway) C++14
18 / 100
 242 ms 24964 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 <int> perm ,ori;

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[ori[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[ori[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) {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    n = N; assert(U.size() == N-1);

    perm.resize(n-1) ,ori.resize(n-1);
    iota(perm.begin() ,perm.end() ,0);
    shuffle(perm.begin() ,perm.end() ,rng);
    vector <int> u(n-1) ,v(n-1);
    for(int i=0; i<n-1; i++){
        ori[perm[i]] = i;
        u[perm[i]] = U[i] ,v[perm[i]] = V[i];
    }

    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[ori[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:42: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:63:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     n = N; assert(U.size() == N-1);
                   ~~~~~~~~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 6 ms 4812 KB Output is correct
3 Correct 7 ms 4856 KB Output is correct
4 Correct 7 ms 4856 KB Output is correct
5 Correct 8 ms 4816 KB Output is correct
6 Correct 6 ms 4856 KB Output is correct
7 Correct 7 ms 4984 KB Output is correct
8 Correct 6 ms 4896 KB Output is correct
9 Correct 7 ms 4856 KB Output is correct
10 Correct 7 ms 4820 KB Output is correct
11 Correct 7 ms 4856 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 5 ms 4888 KB Output is correct
2 Correct 20 ms 5904 KB Output is correct
3 Correct 175 ms 12728 KB Output is correct
4 Correct 143 ms 12888 KB Output is correct
5 Correct 174 ms 12852 KB Output is correct
6 Correct 205 ms 12716 KB Output is correct
7 Correct 196 ms 12872 KB Output is correct
8 Correct 196 ms 12844 KB Output is correct
9 Correct 190 ms 12776 KB Output is correct
10 Correct 210 ms 12776 KB Output is correct
11 Correct 212 ms 14604 KB Output is correct
12 Correct 230 ms 16892 KB Output is correct
13 Correct 217 ms 14872 KB Output is correct
14 Correct 149 ms 15268 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6916 KB Output is correct
2 Correct 73 ms 8420 KB Output is correct
3 Correct 73 ms 11264 KB Output is correct
4 Correct 209 ms 18836 KB Output is correct
5 Correct 210 ms 20364 KB Output is correct
6 Correct 199 ms 19316 KB Output is correct
7 Correct 201 ms 24964 KB Output is correct
8 Correct 201 ms 21244 KB Output is correct
9 Correct 173 ms 22268 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 29 ms 5768 KB Output is correct
3 Correct 139 ms 11112 KB Output is correct
4 Correct 196 ms 12728 KB Output is correct
5 Correct 213 ms 12700 KB Output is correct
6 Correct 161 ms 12776 KB Output is correct
7 Correct 205 ms 12704 KB Output is correct
8 Correct 179 ms 12712 KB Output is correct
9 Correct 206 ms 12748 KB Output is correct
10 Correct 197 ms 12760 KB Output is correct
11 Correct 214 ms 14576 KB Output is correct
12 Correct 223 ms 16392 KB Output is correct
13 Correct 242 ms 14720 KB Output is correct
14 Correct 205 ms 15500 KB Output is correct
15 Correct 199 ms 12800 KB Output is correct
16 Correct 190 ms 12784 KB Output is correct
17 Correct 212 ms 14408 KB Output is correct
18 Correct 204 ms 15688 KB Output is correct
19 Correct 226 ms 12780 KB Output is correct
20 Correct 199 ms 16908 KB Output is correct
21 Correct 166 ms 12936 KB Output is correct
22 Correct 197 ms 12952 KB Output is correct
23 Incorrect 181 ms 13204 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 9368 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 -