oj.uz

Submission #113665

# Submission time Handle Problem Language Result Execution time Memory
113665 2019-05-27T15:29:04 Z zoooma13 Highway Tolls (IOI18_highway) C++14
18 / 100
 283 ms 27364 KB 
#include "highway.h"
#include "bits/stdc++.h"
using namespace std;

#define MAX_N 90004

int qs = 0;
long long Ask(vector<int> w){
    if(++qs > 60)
        assert(0);
    return ask(w);
}

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:49: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:70: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 7 ms 4856 KB Output is correct
2 Correct 7 ms 4900 KB Output is correct
3 Correct 7 ms 4856 KB Output is correct
4 Correct 6 ms 4820 KB Output is correct
5 Correct 7 ms 4816 KB Output is correct
6 Correct 7 ms 4904 KB Output is correct
7 Correct 7 ms 4904 KB Output is correct
8 Correct 6 ms 4860 KB Output is correct
9 Correct 6 ms 4812 KB Output is correct
10 Correct 6 ms 4896 KB Output is correct
11 Correct 8 ms 4816 KB Output is correct
12 Correct 7 ms 4896 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4972 KB Output is correct
2 Correct 28 ms 5800 KB Output is correct
3 Correct 220 ms 13168 KB Output is correct
4 Correct 218 ms 13028 KB Output is correct
5 Correct 194 ms 13164 KB Output is correct
6 Correct 214 ms 12912 KB Output is correct
7 Correct 207 ms 13272 KB Output is correct
8 Correct 213 ms 13184 KB Output is correct
9 Correct 202 ms 13160 KB Output is correct
10 Correct 194 ms 13232 KB Output is correct
11 Correct 211 ms 15336 KB Output is correct
12 Correct 214 ms 17136 KB Output is correct
13 Correct 214 ms 15876 KB Output is correct
14 Correct 217 ms 16088 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6944 KB Output is correct
2 Correct 53 ms 8608 KB Output is correct
3 Correct 74 ms 11392 KB Output is correct
4 Correct 178 ms 18916 KB Output is correct
5 Correct 203 ms 20708 KB Output is correct
6 Correct 208 ms 22332 KB Output is correct
7 Correct 228 ms 25408 KB Output is correct
8 Correct 213 ms 19296 KB Output is correct
9 Correct 205 ms 22628 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 28 ms 5752 KB Output is correct
3 Correct 156 ms 11308 KB Output is correct
4 Correct 199 ms 13000 KB Output is correct
5 Correct 198 ms 13084 KB Output is correct
6 Correct 199 ms 13260 KB Output is correct
7 Correct 190 ms 13068 KB Output is correct
8 Correct 199 ms 13128 KB Output is correct
9 Correct 203 ms 12876 KB Output is correct
10 Correct 187 ms 12976 KB Output is correct
11 Correct 283 ms 14368 KB Output is correct
12 Correct 224 ms 14980 KB Output is correct
13 Correct 214 ms 15760 KB Output is correct
14 Correct 228 ms 16400 KB Output is correct
15 Correct 187 ms 13200 KB Output is correct
16 Correct 176 ms 13172 KB Output is correct
17 Correct 238 ms 15208 KB Output is correct
18 Correct 196 ms 16780 KB Output is correct
19 Correct 189 ms 13192 KB Output is correct
20 Correct 239 ms 17396 KB Output is correct
21 Correct 176 ms 13296 KB Output is correct
22 Correct 185 ms 13288 KB Output is correct
23 Runtime error 224 ms 27364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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