oj.uz

Submission #784170

# Submission time Handle Problem Language Result Execution time Memory
784170 2023-07-15T19:58:47 Z Ozy Highway Tolls (IOI18_highway) C++17
12 / 100
 100 ms 10340 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 90000
//para los hijos
#define des first
#define id second

lli m,df,prof;
lli arista_padre[MAX+2];
vector<pll> hijos[MAX+2];
vector<lli> nodos;

void dfs(lli pos, lli padre, lli p) {

    if(p == prof) {
        nodos.push_back(pos);
        return;
    }

    for(auto h : hijos[pos]) {
        if(padre == h.des) continue;
        arista_padre[h.des] = h.id;
        dfs(h.des,pos,p+1);
    }
}

void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B) {

    m = u.size();
    rep(i,0,m-1) {
        hijos[u[i]].push_back({v[i],i});
        hijos[v[i]].push_back({u[i],i});
    }

    vector<int> status;
    status.resize(m);
    rep(i,0,m-1) status[i] = 0;

    df = ask(status);
    prof = df/A;
    dfs(0,-1,0);

    lli last,ini = 0;
    lli mitad,fin = nodos.size()-1;
    while (ini <= fin) {
        mitad = (ini+fin)/2;
        rep(i,0,nodos.size()-1) {
            if (ini <= i && i <= mitad) status[ arista_padre[nodos[i]] ] = 1;
            else status[arista_padre[nodos[i]]] = 0;
        }

        lli x = ask(status);
        if (x != df) {
            fin = mitad-1;
            last = mitad;
        }
        else ini = mitad+1;
    }

    answer(0,nodos[last]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:7:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i,a,b) for(int i = (a); i <= (b); i++)
      |                                       ^
highway.cpp:55:9: note: in expansion of macro 'rep'
   55 |         rep(i,0,nodos.size()-1) {
      |         ^~~
highway.cpp:68:24: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |     answer(0,nodos[last]);
      |                        ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 7 ms 3152 KB Output is correct
3 Correct 87 ms 9716 KB Output is correct
4 Correct 74 ms 9696 KB Output is correct
5 Correct 64 ms 9700 KB Output is correct
6 Correct 62 ms 9560 KB Output is correct
7 Correct 58 ms 9544 KB Output is correct
8 Correct 62 ms 9660 KB Output is correct
9 Correct 56 ms 9532 KB Output is correct
10 Correct 100 ms 9744 KB Output is correct
11 Correct 71 ms 9760 KB Output is correct
12 Correct 78 ms 10164 KB Output is correct
13 Correct 82 ms 10020 KB Output is correct
14 Correct 66 ms 10340 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3024 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 3 ms 2488 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 16 ms 4428 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 13 ms 3264 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -