oj.uz

Submission #782416

# Submission time Handle Problem Language Result Execution time Memory
782416 2023-07-14T00:03:00 Z vjudge1 Highway Tolls (IOI18_highway) C++17
51 / 100
 206 ms 262144 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> adj[100100];
int dep[100100], par[100100];
vector<int> x;
void dfs(int n, int p = -1, int d = 0) {
    dep[n] = d;
    for(auto i: adj[n])
        if(i.first!=p)
            dfs(i.first, n, d+1), par[i.first] = i.second;
    x.push_back(n);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    for(int i = 0; i < N-1; i++)
        adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});
    dfs(0);
    int M = U.size();
    std::vector<int> w(M, 0);
    long long toll = ask(w);
    int dis = toll/A;
    while(x.size() > 1) {
        vector<int> a,b,c(N-1,0);
        for(int i = 0; i < x.size()/2; i++) {
            a.push_back(x[i]);
            c[par[x[i]]] = 1;
        }
        for(int i = x.size()/2; i < x.size(); i++) {
            b.push_back(x[i]);
        }
        if(ask(c)>toll)
            x = a;
        else 
            x = b;
    }
    int temp = x[0];
    dfs(x[0]);
    x.clear();
    for(int i = 0; i < N; i++)
        if(dep[i]==dis)
            x.push_back(i);
    while(x.size() > 1) {
        vector<int> a,b,c(N-1,0);
        for(int i = 0; i < x.size()/2; i++) {
            a.push_back(x[i]);
            c[par[x[i]]] = 1;
        }
        for(int i = x.size()/2; i < x.size(); i++) {
            b.push_back(x[i]);
        }
        if(ask(c)>toll)
            x = a;
        else 
            x = b;
    }
    answer(temp, x[0]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:24:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i = 0; i < x.size()/2; i++) {
      |                        ~~^~~~~~~~~~~~
highway.cpp:28:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i = x.size()/2; i < x.size(); i++) {
      |                                 ~~^~~~~~~~~~
highway.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i = 0; i < x.size()/2; i++) {
      |                        ~~^~~~~~~~~~~~
highway.cpp:48:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i = x.size()/2; i < x.size(); i++) {
      |                                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 11 ms 3364 KB Output is correct
3 Correct 98 ms 9732 KB Output is correct
4 Correct 90 ms 9812 KB Output is correct
5 Correct 92 ms 9744 KB Output is correct
6 Correct 93 ms 9804 KB Output is correct
7 Correct 104 ms 9748 KB Output is correct
8 Correct 75 ms 9808 KB Output is correct
9 Correct 70 ms 9808 KB Output is correct
10 Correct 79 ms 9796 KB Output is correct
11 Correct 84 ms 10888 KB Output is correct
12 Correct 92 ms 11712 KB Output is correct
13 Correct 83 ms 11120 KB Output is correct
14 Correct 67 ms 10752 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4140 KB Output is correct
2 Correct 17 ms 5604 KB Output is correct
3 Correct 28 ms 7104 KB Output is correct
4 Correct 67 ms 16304 KB Output is correct
5 Correct 86 ms 16304 KB Output is correct
6 Correct 77 ms 16272 KB Output is correct
7 Correct 83 ms 16268 KB Output is correct
8 Correct 69 ms 16228 KB Output is correct
9 Correct 77 ms 16272 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 11 ms 3408 KB Output is correct
3 Correct 90 ms 8212 KB Output is correct
4 Correct 121 ms 9740 KB Output is correct
5 Correct 83 ms 9792 KB Output is correct
6 Correct 85 ms 9800 KB Output is correct
7 Correct 82 ms 9756 KB Output is correct
8 Correct 84 ms 9796 KB Output is correct
9 Correct 84 ms 9796 KB Output is correct
10 Correct 92 ms 9748 KB Output is correct
11 Correct 109 ms 10252 KB Output is correct
12 Correct 97 ms 11788 KB Output is correct
13 Correct 84 ms 11204 KB Output is correct
14 Correct 93 ms 11660 KB Output is correct
15 Correct 87 ms 9808 KB Output is correct
16 Correct 93 ms 9748 KB Output is correct
17 Correct 83 ms 11388 KB Output is correct
18 Correct 109 ms 11080 KB Output is correct
19 Correct 122 ms 9752 KB Output is correct
20 Correct 77 ms 12264 KB Output is correct
21 Correct 91 ms 9988 KB Output is correct
22 Correct 97 ms 9996 KB Output is correct
23 Correct 87 ms 10040 KB Output is correct
24 Correct 90 ms 10628 KB Output is correct
25 Correct 77 ms 15180 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 201 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 206 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -