oj.uz

Submission #615376

# Submission time Handle Problem Language Result Execution time Memory
615376 2022-07-31T08:42:39 Z fvogel499 Highway Tolls (IOI18_highway) C++17
100 / 100
 541 ms 47816 KB 
#include "highway.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define vi vector<int>
#define pii pair<int, int>
#define f first
#define s second
#define sz(x) (int)((x).size())
 
const int siz = 1e6+40;
int nbE;
vector<pii> graph [siz];
int dist [2][siz];
bool incl [2][siz];
int used [2][siz];
 
int caller(vector<int> where) {
    vector<signed> u(nbE, 0);
    for (int i : where) {
        u[i] = 1; // se heavy
    }
    int r = ask(u);
    return r;
}
 
void bfs(const int t, int src) {
    queue<int> q;
    q.push(src);
    dist[t][src] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (pii y : graph[x]) {
            if (dist[t][y.f] == -1) {
                dist[t][y.f] = dist[t][x] + 1;
                q.push(y.f);
                used[t][y.f] = y.s;
                incl[t][y.s] = true;
            }
        }
    }
}
 
int whoIncrease(vi edgeSet, int refD) {
    int x = 0;
    for (int i = (1<<20); i; i /= 2) {
        int prop = x+i;
        if (prop > sz(edgeSet)) continue;
        vi where;
        for (int j = 0; j < prop; j++) {
            where.push_back(edgeSet[j]);
        }
        int r = caller(where);
        assert(r >= refD);
        if (r == refD) {
            x = prop;
        }
    }
    return edgeSet[x];
}
 
void find_pair(const signed n, std::vector<signed> edgeX, std::vector<signed> edgeY, signed aK, signed bK) {
    for (int i = 0; i < n; i++) graph[i].clear();
    nbE = sz(edgeX);
    int distVert = caller({});
    vi allEdges;
    for (int i = 0; i < nbE; i++) {
        allEdges.push_back(i);
    }
    const int magicEdge = whoIncrease(allEdges, distVert);
    for (int i = 0; i < nbE; i++) {
        graph[edgeX[i]].push_back({edgeY[i], i});
        graph[edgeY[i]].push_back({edgeX[i], i});
    }
    for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) dist[i][j] = -1;
    for (int i = 0; i < nbE; i++) {
        incl[0][i] = incl[1][i] = false;
        used[0][i] = used[1][i] = -1;
    }
    bfs(0, edgeX[magicEdge]);
    bfs(1, edgeY[magicEdge]);
    for (int i = 0; i < n; i++) {
        assert(dist[0][i] != -1 && dist[1][i] != -1);
        if (dist[0][i] < dist[1][i]) {
            dist[1][i] = -1;
        }
        else {
            dist[0][i] = -1;
        }
    }
    // vi between;
    // for (int i = 0; i < nbE; i++) if (i != magicEdge) {
    //     if ((dist[0][edgeX[i]] == -1) != (dist[0][edgeY[i]] == -1)) {
    //         between.push_back(i);
    //     }
    // }
    vi res;
    for (int t = 0; t < 2; t++) {
        vector<pair<int, int>> cand;
        for (int i = 0; i < n; i++) if (dist[t][i] != -1 && used[t][i] != -1) {
            cand.push_back({dist[t][i], used[t][i]});
        }
        set<int> lftEdges;
        for (int i = 0; i < nbE; i++) if (i != magicEdge) lftEdges.insert(i);
        for (int i = 0; i < n; i++) if (dist[!t][i] != -1 && used[!t][i] != -1) {
            lftEdges.erase(used[!t][i]);
        }
        for (pii i : cand) lftEdges.erase(i.s);
        sort(cand.begin(), cand.end());
        int bs = -1;
        for (int i = (1<<20); i; i /= 2) {
            int prop = bs+i;
            if (prop >= sz(cand)) continue;
            vi where;
            for (int j = prop; j < sz(cand); j++) {
                where.push_back(cand[j].s);
            }
            // for (int j : between) {
            //     where.push_back(j);
            // }
            for (int j : lftEdges) {
                where.push_back(j);
            }
            int loc = caller(where);
            if (loc > distVert) {
                bs = prop;
            }
        }
        if (bs == -1 || bs == sz(cand)) {
            if (t == 0) {
                res.push_back(edgeX[magicEdge]);
            }
            else {
                res.push_back(edgeY[magicEdge]);
            }
            continue;
        }
        int loc;
        if (dist[t][edgeX[cand[bs].second]] > dist[t][edgeY[cand[bs].second]]) {
            loc = edgeX[cand[bs].second];
        } else {
            loc = edgeY[cand[bs].second];
        }
        res.push_back(loc);
    }
    answer(res[0], res[1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23720 KB Output is correct
2 Correct 15 ms 23744 KB Output is correct
3 Correct 15 ms 23792 KB Output is correct
4 Correct 15 ms 23760 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 13 ms 23796 KB Output is correct
7 Correct 16 ms 23760 KB Output is correct
8 Correct 14 ms 23760 KB Output is correct
9 Correct 15 ms 23760 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 14 ms 23836 KB Output is correct
12 Correct 15 ms 23760 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23920 KB Output is correct
2 Correct 33 ms 25484 KB Output is correct
3 Correct 240 ms 39220 KB Output is correct
4 Correct 224 ms 39212 KB Output is correct
5 Correct 305 ms 39316 KB Output is correct
6 Correct 241 ms 39200 KB Output is correct
7 Correct 300 ms 39220 KB Output is correct
8 Correct 286 ms 39688 KB Output is correct
9 Correct 238 ms 39276 KB Output is correct
10 Correct 239 ms 39208 KB Output is correct
11 Correct 242 ms 38868 KB Output is correct
12 Correct 314 ms 39044 KB Output is correct
13 Correct 317 ms 39276 KB Output is correct
14 Correct 241 ms 39144 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 25372 KB Output is correct
2 Correct 46 ms 27024 KB Output is correct
3 Correct 83 ms 28708 KB Output is correct
4 Correct 163 ms 38420 KB Output is correct
5 Correct 162 ms 38428 KB Output is correct
6 Correct 163 ms 38464 KB Output is correct
7 Correct 175 ms 38728 KB Output is correct
8 Correct 160 ms 38384 KB Output is correct
9 Correct 233 ms 38580 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23888 KB Output is correct
2 Correct 36 ms 25408 KB Output is correct
3 Correct 211 ms 36880 KB Output is correct
4 Correct 234 ms 39260 KB Output is correct
5 Correct 262 ms 39212 KB Output is correct
6 Correct 270 ms 39200 KB Output is correct
7 Correct 247 ms 39220 KB Output is correct
8 Correct 246 ms 39200 KB Output is correct
9 Correct 324 ms 39108 KB Output is correct
10 Correct 293 ms 39172 KB Output is correct
11 Correct 268 ms 39232 KB Output is correct
12 Correct 282 ms 39300 KB Output is correct
13 Correct 286 ms 39052 KB Output is correct
14 Correct 298 ms 38788 KB Output is correct
15 Correct 259 ms 39756 KB Output is correct
16 Correct 269 ms 40000 KB Output is correct
17 Correct 252 ms 39136 KB Output is correct
18 Correct 241 ms 39196 KB Output is correct
19 Correct 254 ms 39272 KB Output is correct
20 Correct 255 ms 39280 KB Output is correct
21 Correct 245 ms 39872 KB Output is correct
22 Correct 228 ms 38808 KB Output is correct
23 Correct 244 ms 38424 KB Output is correct
24 Correct 215 ms 38424 KB Output is correct
25 Correct 272 ms 39100 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 25816 KB Output is correct
2 Correct 45 ms 26048 KB Output is correct
3 Correct 292 ms 41456 KB Output is correct
4 Correct 409 ms 42944 KB Output is correct
5 Correct 531 ms 47100 KB Output is correct
6 Correct 397 ms 47816 KB Output is correct
7 Correct 422 ms 46900 KB Output is correct
8 Correct 488 ms 46684 KB Output is correct
9 Correct 306 ms 43768 KB Output is correct
10 Correct 367 ms 44812 KB Output is correct
11 Correct 345 ms 44468 KB Output is correct
12 Correct 442 ms 46160 KB Output is correct
13 Correct 511 ms 46440 KB Output is correct
14 Correct 423 ms 46576 KB Output is correct
15 Correct 452 ms 46568 KB Output is correct
16 Correct 353 ms 45112 KB Output is correct
17 Correct 229 ms 40312 KB Output is correct
18 Correct 254 ms 40164 KB Output is correct
19 Correct 249 ms 40608 KB Output is correct
20 Correct 231 ms 40464 KB Output is correct
21 Correct 394 ms 47392 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 25812 KB Output is correct
2 Correct 41 ms 25800 KB Output is correct
3 Correct 299 ms 42268 KB Output is correct
4 Correct 344 ms 43084 KB Output is correct
5 Correct 374 ms 43992 KB Output is correct
6 Correct 541 ms 46600 KB Output is correct
7 Correct 300 ms 42828 KB Output is correct
8 Correct 336 ms 43492 KB Output is correct
9 Correct 426 ms 43232 KB Output is correct
10 Correct 445 ms 46796 KB Output is correct
11 Correct 448 ms 46616 KB Output is correct
12 Correct 455 ms 46544 KB Output is correct
13 Correct 345 ms 45116 KB Output is correct
14 Correct 383 ms 44624 KB Output is correct
15 Correct 365 ms 45120 KB Output is correct
16 Correct 359 ms 44768 KB Output is correct
17 Correct 368 ms 45300 KB Output is correct
18 Correct 343 ms 44532 KB Output is correct
19 Correct 425 ms 46160 KB Output is correct
20 Correct 495 ms 46276 KB Output is correct
21 Correct 427 ms 46684 KB Output is correct
22 Correct 437 ms 46600 KB Output is correct
23 Correct 464 ms 46512 KB Output is correct
24 Correct 484 ms 46592 KB Output is correct
25 Correct 436 ms 46380 KB Output is correct
26 Correct 464 ms 46420 KB Output is correct
27 Correct 286 ms 40636 KB Output is correct
28 Correct 254 ms 40324 KB Output is correct
29 Correct 291 ms 41376 KB Output is correct
30 Correct 270 ms 40700 KB Output is correct
31 Correct 259 ms 39860 KB Output is correct
32 Correct 228 ms 40472 KB Output is correct
33 Correct 253 ms 40884 KB Output is correct
34 Correct 208 ms 40516 KB Output is correct
35 Correct 205 ms 39776 KB Output is correct
36 Correct 262 ms 40160 KB Output is correct
37 Correct 272 ms 40920 KB Output is correct
38 Correct 196 ms 41060 KB Output is correct
39 Correct 425 ms 47228 KB Output is correct
40 Correct 438 ms 46892 KB Output is correct
41 Correct 387 ms 46860 KB Output is correct
42 Correct 473 ms 46620 KB Output is correct