oj.uz

Submission #523756

# Submission time Handle Problem Language Result Execution time Memory
523756 2022-02-08T06:18:38 Z InternetPerson10 Highway Tolls (IOI18_highway) C++17
51 / 100
 200 ms 20556 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

pair<int, int> rootedTree(int N, vector<int> U, vector<int> V, int A, int B, ll dep = 0, int root = 0) { // tree, one is determined (by default 0)
    int M = U.size();
    vector<int> v(M, 1);
    if(dep == 0) dep = ask(v) / B;
    vector<vector<pair<int, int>>> adj(N);
    for(int i = 0; i < M; i++) {
        if(U[i] < 0) break;
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    queue<pair<int, pair<int, int>>> q;
    vector<pair<int, int>> candidates;
    vector<bool> taken(N, false);
    q.push({0, {root, -1}});
    while(q.size()) {
        auto p = q.front(); q.pop();
        // cout << p.first << ' ' << p.second.first << '\n';
        taken[p.second.first] = true;
        if(p.first == dep) {
            candidates.push_back(p.second); 
            continue;
        }
        for(auto g : adj[p.second.first]) {
            if(taken[g.first]) continue;
            q.push({p.first + 1, g});
        }
    }
    int g = 1;
    while((1 << g) < candidates.size()) g++;
    ll ans = 0;
    for(int i = 0; i < g; i++) {
        for(int j = 0; j < candidates.size(); j++) {
            if(j & (1 << i)) v[candidates[j].second] = 0;
        }
        if(ask(v) != dep * B) ans += (1 << i);
        for(int j = 0; j < candidates.size(); j++) {
            v[candidates[j].second] = 1;
        }
    }
    // cout << candidates.size() << " candidates\n";
    return {root, candidates[ans].first};
}

pair<int, int> generalTree(int N, vector<int> U, vector<int> V, int A, int B) { // tree
    int M = U.size();
    vector<int> v(M, 1);
    vector<vector<pair<int, int>>> adj(N);
    vector<vector<pair<int, int>>> depths(N);
    for(int i = 0; i < M; i++) {
        if(U[i] < 0) break;
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    vector<bool> taken(N, false);
    queue<pair<int, pair<int, int>>> q;
    q.push({0, {0, -1}});
    while(q.size()) {
        auto p = q.front(); q.pop();
        taken[p.second.first] = true;
        depths[p.first].push_back(p.second);
        for(auto g : adj[p.second.first]) {
            if(taken[g.first]) continue;
            q.push({p.first + 1, g});
        }
    }
    while(depths.back().size() == 0) depths.pop_back();
    ll largeLength = ask(v);
    int l = 1, r = depths.size();
    while(l != r - 1) {
        int mid = (l + r) / 2;
        for(int i = mid; i < depths.size(); i++) {
            for(auto g : depths[i]) {
                v[g.second] = 0;
            }
        }
        if(ask(v) == largeLength) r = mid;
        else l = mid;
        for(int i = mid; i < depths.size(); i++) {
            for(auto g : depths[i]) {
                v[g.second] = 1;
            }
        }
    }
    int g = 0;
    while((1 << g) < depths[l].size()) g++;
    int ans = 0;
    for(int i = 0; i < g; i++) { // Funny way to divide people into two groups, check for good
        for(int j = 0; j < depths[l].size(); j++) {
            if((j ^ ans) % (1 << i)) continue;
            if(j & (1 << i)) v[depths[l][j].second] = 0;
        }
        if(ask(v) != largeLength) ans += (1 << i);
        for(int j = 0; j < depths[l].size(); j++) {
            if((j ^ ans) % (1 << i)) continue;
            if(j & (1 << i)) v[depths[l][j].second] = 1;
        }
    }
    // cout << "Determined one of them to be " << depths[l][ans].first << '\n';
    return rootedTree(N, U, V, A, B, 0, depths[l][ans].first);
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    pair<int, int> ans;
    if(U.size() + 1 == N) ans = generalTree(N, U, V, A, B);    
    else {

    }
    answer(ans.first, ans.second);
}

Compilation message

highway.cpp: In function 'std::pair<int, int> rootedTree(int, std::vector<int>, std::vector<int>, int, int, ll, int)':
highway.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while((1 << g) < candidates.size()) g++;
      |           ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
highway.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j = 0; j < candidates.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
highway.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int j = 0; j < candidates.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
highway.cpp: In function 'std::pair<int, int> generalTree(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:77:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int i = mid; i < depths.size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~
highway.cpp:84:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int i = mid; i < depths.size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~
highway.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     while((1 << g) < depths[l].size()) g++;
      |           ~~~~~~~~~^~~~~~~~~~~~~~~~~~
highway.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int j = 0; j < depths[l].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~
highway.cpp:99:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int j = 0; j < depths[l].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:110:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |     if(U.size() + 1 == N) ans = generalTree(N, U, V, A, B);
      |        ~~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 456 KB Output is correct
2 Correct 13 ms 2248 KB Output is correct
3 Correct 174 ms 18116 KB Output is correct
4 Correct 124 ms 17952 KB Output is correct
5 Correct 137 ms 18124 KB Output is correct
6 Correct 125 ms 17836 KB Output is correct
7 Correct 153 ms 18056 KB Output is correct
8 Correct 118 ms 17752 KB Output is correct
9 Correct 145 ms 18076 KB Output is correct
10 Correct 125 ms 17956 KB Output is correct
11 Correct 199 ms 16988 KB Output is correct
12 Correct 136 ms 17264 KB Output is correct
13 Correct 125 ms 17112 KB Output is correct
14 Correct 164 ms 16912 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2324 KB Output is correct
2 Correct 51 ms 4436 KB Output is correct
3 Correct 45 ms 6352 KB Output is correct
4 Correct 149 ms 18556 KB Output is correct
5 Correct 120 ms 18544 KB Output is correct
6 Correct 99 ms 18564 KB Output is correct
7 Correct 140 ms 18668 KB Output is correct
8 Correct 110 ms 18836 KB Output is correct
9 Correct 138 ms 18568 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 420 KB Output is correct
2 Correct 18 ms 2280 KB Output is correct
3 Correct 90 ms 13912 KB Output is correct
4 Correct 114 ms 17760 KB Output is correct
5 Correct 156 ms 17740 KB Output is correct
6 Correct 144 ms 17716 KB Output is correct
7 Correct 163 ms 17772 KB Output is correct
8 Correct 121 ms 17696 KB Output is correct
9 Correct 161 ms 18016 KB Output is correct
10 Correct 172 ms 18064 KB Output is correct
11 Correct 150 ms 17032 KB Output is correct
12 Correct 129 ms 17188 KB Output is correct
13 Correct 156 ms 17116 KB Output is correct
14 Correct 134 ms 17224 KB Output is correct
15 Correct 139 ms 17708 KB Output is correct
16 Correct 132 ms 17640 KB Output is correct
17 Correct 124 ms 17192 KB Output is correct
18 Correct 116 ms 17040 KB Output is correct
19 Correct 158 ms 17720 KB Output is correct
20 Correct 116 ms 17324 KB Output is correct
21 Correct 158 ms 20500 KB Output is correct
22 Correct 177 ms 20556 KB Output is correct
23 Correct 200 ms 19236 KB Output is correct
24 Correct 137 ms 19220 KB Output is correct
25 Correct 142 ms 18608 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 456 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 356 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -