oj.uz

답안 #1077889

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077889 2024-08-27T10:08:49 Z vladilius 통행료 (IOI18_highway) C++17
0 / 100
 19 ms 7724 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 (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), p(n), pe(n);
    function<void(int, int, int, vector<pii>&, vector<int>&)> dfs = [&](int v, int pr, int ed, vector<pii>& k, vector<int>& t){
        t.pb(v);
        p[v] = pr; pe[v] = ed;
        if (ed != -1) k.pb({pr, 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<pii> c1, c2;
    vector<int> q1, q2;
    d[x] = d[y] = 0;
    dfs(x, 0, -1, c1, q1);
    dfs(y, 0, -1, c2, q2);
    
    auto add = [&](int v){
        while (v > 0){
            w[pe[v]] = 1;
            v = p[v];
        }
    };
    
    nl /= A;
    
    auto solve = [&](vector<pii> t1, vector<pii> t2, vector<int> q){
        em();
        for (auto [i, 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: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:101:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |                 while (all.size() > m) all.pop_back();
      |                        ~~~~~~~~~~~^~~
highway.cpp:106:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |                 while (all.size() > m) all.pop_back();
      |                        ~~~~~~~~~~~^~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2648 KB Output is correct
2 Runtime error 19 ms 7724 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 600 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 512 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -