oj.uz

Submission #1013804

# Submission time Handle Problem Language Result Execution time Memory
1013804 2024-07-04T06:10:49 Z 김은성(#10850) Highway Tolls (IOI18_highway) C++17
12 / 100
 70 ms 9748 KB 
#define SUB
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int, int> > graph[90009];
int edge[90009];
int depth[90009];
bool ch[90009];
void dfs(int v){
    ch[v] = 1;
    int i;
    for(i=0; i<graph[v].size(); i++){
        int u = graph[v][i].second;
        if(ch[u])
            continue;
        edge[u] = graph[v][i].first;
        depth[u] = depth[v] + 1;
        dfs(u);
    }
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    #ifdef SUB
    int M = U.size(), i;
    vector<int> toll(M);
    for(i=0; i<M; i++){
        graph[U[i]].push_back(make_pair(i, V[i]));
        graph[V[i]].push_back(make_pair(i, U[i]));
    }
    dfs(0);
    ll ret = ask(toll);
    int d = (ll)ret / A;
    vector<pair<int, int> > e;
    for(i=0; i<N; i++){
        if(depth[i] == d){
            e.push_back(make_pair(edge[i], i));
        }
    }
    int lo = 0, hi = (int)e.size() - 1, mid;
    while(lo < hi){
        mid = (lo+hi)/2;
        for(i=0; i<=mid; i++)
            toll[e[i].first] = 1;
        for(i=mid+1; i<=hi; i++)
            toll[e[i].first] = 0;
        ll ret2 = ask(toll);
        if(ret != ret2)
            hi = mid;
        else
            lo = mid+1;
    }
    answer(0, e[lo].second);
    #endif // SUB
    #ifndef SUB
    s
    #endif // SUB
}

Compilation message

highway.cpp: In function 'void dfs(int)':
highway.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(i=0; i<graph[v].size(); i++){
      |              ~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 8 ms 3672 KB Output is correct
3 Correct 60 ms 8680 KB Output is correct
4 Correct 66 ms 8676 KB Output is correct
5 Correct 67 ms 8684 KB Output is correct
6 Correct 58 ms 8484 KB Output is correct
7 Correct 62 ms 8580 KB Output is correct
8 Correct 58 ms 8696 KB Output is correct
9 Correct 58 ms 8492 KB Output is correct
10 Correct 51 ms 8668 KB Output is correct
11 Correct 70 ms 9228 KB Output is correct
12 Correct 62 ms 9748 KB Output is correct
13 Correct 58 ms 9228 KB Output is correct
14 Correct 57 ms 8784 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

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