oj.uz

Submission #604124

# Submission time Handle Problem Language Result Execution time Memory
604124 2022-07-24T18:41:14 Z AlperenT Highway Tolls (IOI18_highway) C++17
51 / 100
 313 ms 262144 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 9e4, K = 15;

vector<pair<int, int>> graph[N];

vector<int> ones, zeros;

void dfs(int v, int p, bool flag){
    if(flag) ones.push_back(v);
    else zeros.push_back(v);

    for(auto e : graph[v]){
        if(e.first != p){
            dfs(e.first, v, flag ^ 1);
        }
    }
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b){
    int m = u.size(), s = -1, t = -1;

    for(int i = 0; i < m; i++){
        graph[u[i]].push_back({v[i], i});
        graph[v[i]].push_back({u[i], i});
    }

    vector<int> tmp(m, 0);

    long long dist = ask(tmp);

    dfs(0, -1, 0);

    if(zeros.size() > ones.size()) swap(zeros, ones);

    tmp.assign(m, 0);

    for(auto v : ones){
        for(auto e : graph[v]){
            tmp[e.second] = 1;
        }
    }

    if(((ask(tmp) - dist) / (b - a)) % 2 == 1){
        int l = 0, r = ones.size(), md;

        while(r - l > 1){
            md = l + (r - l) / 2;

            tmp.assign(m, 0);

            for(int i = 0; i < md; i++){
                int v = ones[i];

                for(auto e : graph[v]) tmp[e.second] = 1;
            }

            if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
            else l = md;
        }

        s = ones[l];

        l = 0, r = zeros.size();

        while(r - l > 1){
            md = l + (r - l) / 2;

            tmp.assign(m, 0);

            for(int i = 0; i < md; i++){
                int v = zeros[i];

                for(auto e : graph[v]) tmp[e.second] = 1;
            }

            if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
            else l = md;
        }

        t = zeros[l];

        answer(s, t);

        return;
    }
    else{
        for(int it = 0; it < K; it++){
            shuffle(ones.begin(), ones.end(), rng);

            tmp.assign(m, 0);

            for(int i = 0; i <= (ones.size() - 1) / 2; i++){
                int v = ones[i];

                for(auto e : graph[v]) tmp[e.second] = 1;
            }

            if(((ask(tmp) - dist) / (b - a)) % 2 == 1){
                vector<int> seta, setb;

                for(int i = 0; i <= (ones.size() - 1) / 2; i++) seta.push_back(ones[i]);
                for(int i = (ones.size() - 1) / 2 + 1; i < ones.size(); i++) setb.push_back(ones[i]);

                int l = 0, r = seta.size(), md;

                while(r - l > 1){
                    md = l + (r - l) / 2;

                    tmp.assign(m, 0);

                    for(int i = 0; i < md; i++){
                        int v = seta[i];

                        for(auto e : graph[v]) tmp[e.second] = 1;
                    }

                    if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
                    else l = md;
                }

                s = seta[l];

                l = 0, r = setb.size();

                while(r - l > 1){
                    md = l + (r - l) / 2;

                    tmp.assign(m, 0);

                    for(int i = 0; i < md; i++){
                        int v = setb[i];

                        for(auto e : graph[v]) tmp[e.second] = 1;
                    }

                    if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
                    else l = md;
                }

                t = setb[l];

                answer(s, t);

                return;
            }
        }

        for(int it = 0; it < K; it++){
            shuffle(zeros.begin(), zeros.end(), rng);

            tmp.assign(m, 0);

            for(int i = 0; i <= (zeros.size() - 1) / 2; i++){
                int v = zeros[i];

                for(auto e : graph[v]) tmp[e.second] = 1;
            }

            if(((ask(tmp) - dist) / (b - a)) % 2 == 1){
                vector<int> seta, setb;

                for(int i = 0; i <= (zeros.size() - 1) / 2; i++) seta.push_back(zeros[i]);
                for(int i = (zeros.size() - 1) / 2 + 1; i < zeros.size(); i++) setb.push_back(zeros[i]);

                int l = 0, r = seta.size(), md;

                while(r - l > 1){
                    md = l + (r - l) / 2;

                    tmp.assign(m, 0);

                    for(int i = 0; i < md; i++){
                        int v = seta[i];

                        for(auto e : graph[v]) tmp[e.second] = 1;
                    }

                    if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
                    else l = md;
                }

                s = seta[l];

                l = 0, r = setb.size();

                while(r - l > 1){
                    md = l + (r - l) / 2;

                    tmp.assign(m, 0);

                    for(int i = 0; i < md; i++){
                        int v = setb[i];

                        for(auto e : graph[v]) tmp[e.second] = 1;
                    }

                    if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
                    else l = md;
                }

                t = setb[l];

                answer(s, t);

                return;
            }
        }
    }

    assert(false);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:98:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for(int i = 0; i <= (ones.size() - 1) / 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:107:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |                 for(int i = 0; i <= (ones.size() - 1) / 2; i++) seta.push_back(ones[i]);
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:108:58: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 for(int i = (ones.size() - 1) / 2 + 1; i < ones.size(); i++) setb.push_back(ones[i]);
      |                                                        ~~^~~~~~~~~~~~~
highway.cpp:159:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |             for(int i = 0; i <= (zeros.size() - 1) / 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:168:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |                 for(int i = 0; i <= (zeros.size() - 1) / 2; i++) seta.push_back(zeros[i]);
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:169:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |                 for(int i = (zeros.size() - 1) / 2 + 1; i < zeros.size(); i++) setb.push_back(zeros[i]);
      |                                                         ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2472 KB Output is correct
2 Correct 13 ms 2984 KB Output is correct
3 Correct 232 ms 8224 KB Output is correct
4 Correct 313 ms 8216 KB Output is correct
5 Correct 253 ms 8228 KB Output is correct
6 Correct 212 ms 8228 KB Output is correct
7 Correct 178 ms 8224 KB Output is correct
8 Correct 131 ms 8124 KB Output is correct
9 Correct 152 ms 8220 KB Output is correct
10 Correct 231 ms 8228 KB Output is correct
11 Correct 159 ms 8928 KB Output is correct
12 Correct 232 ms 9624 KB Output is correct
13 Correct 168 ms 9160 KB Output is correct
14 Correct 117 ms 8612 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3536 KB Output is correct
2 Correct 20 ms 4748 KB Output is correct
3 Correct 44 ms 6048 KB Output is correct
4 Correct 117 ms 13204 KB Output is correct
5 Correct 172 ms 13304 KB Output is correct
6 Correct 90 ms 13196 KB Output is correct
7 Correct 155 ms 13304 KB Output is correct
8 Correct 90 ms 13204 KB Output is correct
9 Correct 155 ms 13304 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 11 ms 3068 KB Output is correct
3 Correct 113 ms 6976 KB Output is correct
4 Correct 192 ms 8368 KB Output is correct
5 Correct 167 ms 8224 KB Output is correct
6 Correct 241 ms 8272 KB Output is correct
7 Correct 219 ms 8188 KB Output is correct
8 Correct 144 ms 8220 KB Output is correct
9 Correct 184 ms 8308 KB Output is correct
10 Correct 172 ms 8060 KB Output is correct
11 Correct 191 ms 8392 KB Output is correct
12 Correct 202 ms 9812 KB Output is correct
13 Correct 157 ms 9080 KB Output is correct
14 Correct 168 ms 9484 KB Output is correct
15 Correct 114 ms 8152 KB Output is correct
16 Correct 156 ms 8260 KB Output is correct
17 Correct 192 ms 9292 KB Output is correct
18 Correct 206 ms 9064 KB Output is correct
19 Correct 142 ms 8232 KB Output is correct
20 Correct 282 ms 10124 KB Output is correct
21 Correct 184 ms 8760 KB Output is correct
22 Correct 163 ms 8896 KB Output is correct
23 Correct 210 ms 8824 KB Output is correct
24 Correct 198 ms 9328 KB Output is correct
25 Correct 230 ms 12476 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 228 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -