oj.uz

Submission #1077911

# Submission time Handle Problem Language Result Execution time Memory
1077911 2024-08-27T10:27:05 Z vladilius Highway Tolls (IOI18_highway) C++17
51 / 100
 111 ms 19624 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]]){
            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]);
            }
            for (int i = 0; i < n - 1; 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:103:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |                 while (all.size() > m) all.pop_back();
      |                        ~~~~~~~~~~~^~~
highway.cpp:108:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |                 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 0 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 8 ms 1680 KB Output is correct
3 Correct 80 ms 11088 KB Output is correct
4 Correct 76 ms 10848 KB Output is correct
5 Correct 78 ms 11136 KB Output is correct
6 Correct 79 ms 10940 KB Output is correct
7 Correct 77 ms 10880 KB Output is correct
8 Correct 86 ms 10656 KB Output is correct
9 Correct 75 ms 10948 KB Output is correct
10 Correct 78 ms 10956 KB Output is correct
11 Correct 71 ms 12192 KB Output is correct
12 Correct 75 ms 13716 KB Output is correct
13 Correct 75 ms 12636 KB Output is correct
14 Correct 82 ms 12964 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2392 KB Output is correct
2 Correct 14 ms 4184 KB Output is correct
3 Correct 22 ms 6544 KB Output is correct
4 Correct 78 ms 15304 KB Output is correct
5 Correct 67 ms 16432 KB Output is correct
6 Correct 68 ms 17816 KB Output is correct
7 Correct 64 ms 19624 KB Output is correct
8 Correct 66 ms 15280 KB Output is correct
9 Correct 65 ms 18084 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 1604 KB Output is correct
3 Correct 61 ms 8788 KB Output is correct
4 Correct 76 ms 10876 KB Output is correct
5 Correct 69 ms 10928 KB Output is correct
6 Correct 72 ms 10944 KB Output is correct
7 Correct 67 ms 10948 KB Output is correct
8 Correct 65 ms 10936 KB Output is correct
9 Correct 75 ms 11184 KB Output is correct
10 Correct 80 ms 11144 KB Output is correct
11 Correct 67 ms 12500 KB Output is correct
12 Correct 78 ms 13724 KB Output is correct
13 Correct 72 ms 13440 KB Output is correct
14 Correct 74 ms 13732 KB Output is correct
15 Correct 78 ms 10984 KB Output is correct
16 Correct 74 ms 10960 KB Output is correct
17 Correct 91 ms 12704 KB Output is correct
18 Correct 75 ms 13240 KB Output is correct
19 Correct 67 ms 10956 KB Output is correct
20 Correct 73 ms 14248 KB Output is correct
21 Correct 69 ms 11460 KB Output is correct
22 Correct 73 ms 11916 KB Output is correct
23 Correct 78 ms 11420 KB Output is correct
24 Correct 82 ms 11972 KB Output is correct
25 Correct 111 ms 19160 KB Output is correct

Subtask #5
0 / 18.0

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