oj.uz

Submission #1077907

# Submission time Handle Problem Language Result Execution time Memory
1077907 2024-08-27T10:23:42 Z vladilius Highway Tolls (IOI18_highway) C++17
18 / 100
 1500 ms 19632 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert

void find_pair(int n, vector<int> U, vector<int> V, int A, int B){
    if (U.size() != (n - 1)){
        answer(0, 0);
        return;
    }
    vector<pii> g[n + 1];
    for (int i = 0; i < n - 1; i++){
        U[i]++; V[i]++;
        g[U[i]].pb({V[i], i});
        g[V[i]].pb({U[i], i});
    }
    
    vector<int> w(n - 1);
    ll nl = ask(w);
    
    auto em = [&](){
        fill(w.begin(), w.end(), 0);
    };
    
    vector<int> all;
    for (int i = 0; i < n - 1; i++) all.pb(i);
    
    while (all.size() > 1){
        int m = (int) (all.size()) / 2;
        em();
        for (int i = 0; i < m; i++){
            w[all[i]] = 1;
        }
        
        ll g = ask(w);
        if (g == nl){
            reverse(all.begin(), all.end());
            m = (int) all.size() - m;
            while (all.size() > m) all.pop_back();
        }
        else {
            while (all.size() > m) all.pop_back();
        }
    }
    
    int T = all[0], x = U[T], y = V[T];
    
    vector<int> d(n + 1), p(n + 1), pe(n + 1);
    function<void(int, int, int, vector<int>&, vector<int>&)> dfs = [&](int v, int pr, int ed, vector<int>& k, vector<int>& t){
        t.pb(v);
        p[v] = pr; pe[v] = ed;
        if (ed != -1) k.pb(ed);
        for (auto [i, j]: g[v]){
            if (i == pr || j == T) continue;
            d[i] = d[v] + 1;
            dfs(i, v, j, k, t);
        }
    };
    
    vector<int> c1, c2, q1, q2;
    d[x] = d[y] = 0;
    dfs(x, 0, -1, c1, q1);
    dfs(y, 0, -1, c2, q2);
    
    auto add = [&](int v){
        while (pe[v] != -1){
            w[pe[v]] = 1;
            v = p[v];
        }
    };
    
    nl /= A;
    
    auto solve = [&](vector<int> t1, vector<int> t2, vector<int> q){
        em();
        for (int j: t2) w[j] = 1;
        int dd = (int) ((ask(w) - B * (nl - 1) - A) / (A - B));

        vector<int> all;
        for (int i: q){
            if (d[i] == dd){
                all.pb(i);
            }
        }

        while (all.size() > 1){
            int m = (int) (all.size()) / 2;
            em();
            for (int i = 0; i < m; i++){
                add(all[i]);
            }
            
            ll S = ask(w);
            if (S == (1LL * B * dd + 1LL * A * (nl - dd))){
                while (all.size() > m) all.pop_back();
            }
            else {
                reverse(all.begin(), all.end());
                m = (int) all.size() - m;
                while (all.size() > m) all.pop_back();
            }
        }
        
        return (all[0] - 1);
    };
    
    answer(solve(c1, c2, q1), solve(c2, c1, q2));
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:12:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |     if (U.size() != (n - 1)){
      |         ~~~~~~~~~^~~~~~~~~~
highway.cpp:44:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |             while (all.size() > m) all.pop_back();
      |                    ~~~~~~~~~~~^~~
highway.cpp:47:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |             while (all.size() > m) all.pop_back();
      |                    ~~~~~~~~~~~^~~
highway.cpp: In lambda function:
highway.cpp:100:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |                 while (all.size() > m) all.pop_back();
      |                        ~~~~~~~~~~~^~~
highway.cpp:105:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |                 while (all.size() > m) all.pop_back();
      |                        ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 1624 KB Output is correct
3 Correct 91 ms 10936 KB Output is correct
4 Correct 78 ms 10856 KB Output is correct
5 Correct 98 ms 10884 KB Output is correct
6 Correct 85 ms 11176 KB Output is correct
7 Correct 74 ms 10864 KB Output is correct
8 Correct 81 ms 10896 KB Output is correct
9 Correct 84 ms 11180 KB Output is correct
10 Correct 85 ms 11076 KB Output is correct
11 Correct 82 ms 12212 KB Output is correct
12 Correct 87 ms 13940 KB Output is correct
13 Correct 95 ms 12660 KB Output is correct
14 Correct 94 ms 12916 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2300 KB Output is correct
2 Correct 17 ms 4160 KB Output is correct
3 Correct 25 ms 6476 KB Output is correct
4 Correct 64 ms 15300 KB Output is correct
5 Correct 66 ms 16580 KB Output is correct
6 Correct 58 ms 17824 KB Output is correct
7 Correct 70 ms 19632 KB Output is correct
8 Correct 64 ms 15548 KB Output is correct
9 Correct 69 ms 18084 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1624 KB Output is correct
3 Correct 53 ms 8776 KB Output is correct
4 Correct 80 ms 10932 KB Output is correct
5 Correct 76 ms 10960 KB Output is correct
6 Correct 76 ms 10964 KB Output is correct
7 Correct 71 ms 10916 KB Output is correct
8 Correct 68 ms 10920 KB Output is correct
9 Correct 93 ms 11168 KB Output is correct
10 Correct 94 ms 11156 KB Output is correct
11 Correct 79 ms 12476 KB Output is correct
12 Correct 93 ms 13944 KB Output is correct
13 Correct 86 ms 13352 KB Output is correct
14 Correct 75 ms 13780 KB Output is correct
15 Correct 69 ms 10788 KB Output is correct
16 Correct 72 ms 10940 KB Output is correct
17 Correct 80 ms 12724 KB Output is correct
18 Correct 72 ms 13228 KB Output is correct
19 Correct 72 ms 10948 KB Output is correct
20 Correct 76 ms 14252 KB Output is correct
21 Correct 67 ms 11560 KB Output is correct
22 Correct 64 ms 11912 KB Output is correct
23 Correct 458 ms 11420 KB Output is correct
24 Execution timed out 3055 ms 11428 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 600 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 5 ms 600 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -