oj.uz

Submission #250085

# Submission time Handle Problem Language Result Execution time Memory
250085 2020-07-16T23:43:31 Z ant101 Highway Tolls (IOI18_highway) C++14
69 / 100
 386 ms 10096 KB 
#include "highway.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
#include <bitset>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 90005;

vector<int> gph[MAXN];

lint cut_ask(int m, vector<int> &c, vector<int> &u, vector<int> &v){
    bitset<MAXN> vis;
    for(auto &i : c) vis[i] = 1;
    vector<int> query(m);
    for(int i=0; i<m; i++) if(vis[u[i]] != vis[v[i]]) query[i] = 1;
    return ask(query);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    if (!((A == 1 && B == 2) || U.size() == N-1)) {
        return;
    }
    int M = U.size();
    for(int i=0; i<M; i++){
        gph[U[i]].emplace_back(V[i]);
        gph[V[i]].emplace_back(U[i]);
    }
    vector<int> v(M);
    lint stdist = ask(v) / A;
    int s = 0, e = M - 1;
    while(s != e){
        int m = (s + e) / 2;
        fill(v.begin() + m + 1, v.end(), 0);
        fill(v.begin(), v.begin() + m + 1, 1);
        if(ask(v) != A * stdist) e = m;
        else s = m + 1;
    }
    vector<int> bord[2], dist(N, 1e9);
    queue<pi> que;
    que.emplace(0, U[s]);
    que.emplace(1, V[s]);
    dist[U[s]] = dist[V[s]] = 0;
    while(!que.empty()){
        auto x = que.front(); que.pop();
        bord[x.first].push_back(x.second);
        for(auto &i : gph[x.second]){
            if(dist[i] > dist[x.second] + 1){
                dist[i] = dist[x.second] + 1;
                que.emplace(x.first, i);
            }
        }
    }
    int S = -1, T = -1;
    for(int i=0; i<2; i++){
        int s = 0, e = (int)bord[i].size() - 1;
        while(s != e){
            int m = (s + e + 1) / 2;
            vector<int> C(bord[i].begin() + m, bord[i].end());
            if(cut_ask(M, C, U, V) != stdist * A) s = m;
            else e = m - 1;
        }
        if(i) S = bord[i][s];
        else T = bord[i][s];
    }
    answer(S, T);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:36:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (!((A == 1 && B == 2) || U.size() == N-1)) {
                                 ~~~~~~~~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2432 KB Output is correct
2 Correct 2 ms 2432 KB Output is correct
3 Correct 2 ms 2432 KB Output is correct
4 Correct 2 ms 2432 KB Output is correct
5 Correct 2 ms 2432 KB Output is correct
6 Correct 2 ms 2432 KB Output is correct
7 Correct 2 ms 2432 KB Output is correct
8 Correct 2 ms 2432 KB Output is correct
9 Correct 2 ms 2432 KB Output is correct
10 Correct 2 ms 2432 KB Output is correct
11 Correct 2 ms 2432 KB Output is correct
12 Correct 3 ms 2432 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2432 KB Output is correct
2 Correct 14 ms 3328 KB Output is correct
3 Correct 152 ms 8496 KB Output is correct
4 Correct 138 ms 8584 KB Output is correct
5 Correct 140 ms 8552 KB Output is correct
6 Correct 121 ms 8416 KB Output is correct
7 Correct 131 ms 8536 KB Output is correct
8 Correct 252 ms 8664 KB Output is correct
9 Correct 254 ms 8676 KB Output is correct
10 Correct 251 ms 8528 KB Output is correct
11 Correct 135 ms 8540 KB Output is correct
12 Correct 238 ms 8452 KB Output is correct
13 Correct 212 ms 8320 KB Output is correct
14 Correct 256 ms 8432 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3072 KB Output is correct
2 Correct 25 ms 3940 KB Output is correct
3 Correct 36 ms 4416 KB Output is correct
4 Correct 110 ms 8188 KB Output is correct
5 Correct 126 ms 8352 KB Output is correct
6 Correct 112 ms 8320 KB Output is correct
7 Correct 109 ms 8548 KB Output is correct
8 Correct 109 ms 8264 KB Output is correct
9 Correct 106 ms 8308 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2560 KB Output is correct
2 Correct 23 ms 3064 KB Output is correct
3 Correct 104 ms 7296 KB Output is correct
4 Correct 141 ms 8620 KB Output is correct
5 Correct 239 ms 8640 KB Output is correct
6 Correct 243 ms 8620 KB Output is correct
7 Correct 140 ms 8680 KB Output is correct
8 Correct 149 ms 8676 KB Output is correct
9 Correct 244 ms 8628 KB Output is correct
10 Correct 182 ms 8656 KB Output is correct
11 Correct 247 ms 8352 KB Output is correct
12 Correct 121 ms 8424 KB Output is correct
13 Correct 192 ms 8288 KB Output is correct
14 Correct 142 ms 8364 KB Output is correct
15 Correct 212 ms 8732 KB Output is correct
16 Correct 127 ms 8900 KB Output is correct
17 Correct 142 ms 8516 KB Output is correct
18 Correct 137 ms 8380 KB Output is correct
19 Correct 130 ms 8704 KB Output is correct
20 Correct 246 ms 8576 KB Output is correct
21 Correct 115 ms 9224 KB Output is correct
22 Correct 104 ms 9356 KB Output is correct
23 Correct 129 ms 9112 KB Output is correct
24 Correct 139 ms 8928 KB Output is correct
25 Correct 143 ms 8412 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3064 KB Output is correct
2 Correct 21 ms 3320 KB Output is correct
3 Correct 141 ms 8704 KB Output is correct
4 Correct 185 ms 9092 KB Output is correct
5 Correct 323 ms 10096 KB Output is correct
6 Correct 286 ms 9820 KB Output is correct
7 Correct 205 ms 9680 KB Output is correct
8 Correct 229 ms 9816 KB Output is correct
9 Correct 201 ms 7676 KB Output is correct
10 Correct 146 ms 8096 KB Output is correct
11 Correct 244 ms 8160 KB Output is correct
12 Correct 201 ms 9316 KB Output is correct
13 Correct 216 ms 9496 KB Output is correct
14 Correct 230 ms 9628 KB Output is correct
15 Correct 265 ms 9796 KB Output is correct
16 Correct 190 ms 8492 KB Output is correct
17 Correct 159 ms 9192 KB Output is correct
18 Correct 227 ms 9444 KB Output is correct
19 Correct 205 ms 9360 KB Output is correct
20 Correct 147 ms 9448 KB Output is correct
21 Correct 386 ms 9560 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2560 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -