oj.uz

Submission #1074651

# Submission time Handle Problem Language Result Execution time Memory
1074651 2024-08-25T11:42:23 Z wood Highway Tolls (IOI18_highway) C++17
12 / 100
 75 ms 9252 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay


void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int n = N, m = U.size();
    vp32 adj[n];
    int vertex[m];
    for(int i = 0; i<m; i++){
        adj[U[i]].eb(V[i],i);
        adj[V[i]].eb(U[i],i);
    }
    queue<p32> q;
    q.emplace(0,-1);
    p32 depth[n]; memset(depth,0,sizeof depth); depth[0] = p32(1,-1);
    while(!q.empty()){
        p32 x = q.front();
        q.pop();
        for(p32 ii : adj[x.fi]){
            if(!depth[ii.fi].fi){
                depth[ii.fi].fi = depth[x.fi].fi+1;
                depth[ii.fi].se = ii.se;
                q.push(ii);
                vertex[ii.se] = ii.fi;
            }
        }
    }
    vi w(m);
    ll d = ask(w)/A;
    vector<int> v;
    for(int i = 0; i<n ;i++){
        if(depth[i].fi==d+1) v.pb(depth[i].se);
    }
    int l = -1, r = v.size()-1;
    while(r-l>1){
        int mid = (r+l)/2;
        vi soel(m);
        for(int i = l+1; i<=mid; i++){
            soel[v[i]] = 1;
        }
        if(ask(soel)==d*A) l = mid;
        else r = mid;
    }
    answer(0,vertex[v[r]]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:37:46: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'p32' {aka 'struct std::pair<int, int>'} with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   37 |     p32 depth[n]; memset(depth,0,sizeof depth); depth[0] = p32(1,-1);
      |                                              ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from highway.h:3,
                 from highway.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'p32' {aka 'struct std::pair<int, int>'} declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 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 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 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 7 ms 1624 KB Output is correct
3 Correct 73 ms 9184 KB Output is correct
4 Correct 68 ms 9244 KB Output is correct
5 Correct 65 ms 9224 KB Output is correct
6 Correct 69 ms 9072 KB Output is correct
7 Correct 66 ms 9192 KB Output is correct
8 Correct 70 ms 9252 KB Output is correct
9 Correct 75 ms 9040 KB Output is correct
10 Correct 71 ms 9240 KB Output is correct
11 Correct 74 ms 8464 KB Output is correct
12 Correct 64 ms 8528 KB Output is correct
13 Correct 61 ms 8528 KB Output is correct
14 Correct 64 ms 8528 KB Output is correct

Subtask #3
0 / 6.0

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