oj.uz

Submission #1074522

# Submission time Handle Problem Language Result Execution time Memory
1074522 2024-08-25T10:58:18 Z TB_ Highway Tolls (IOI18_highway) C++17
12 / 100
 919 ms 12244 KB 
#include <bits/stdc++.h>
#include "highway.h"


using namespace std;

#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define pb push_back
#define F first
#define S second
#define deb(x) cout << #x << " = " << (x) << endl 
#define deb2(x, y) cout << #x << " = " << (x)  << ", " << #y << " = " << (y) << endl 
typedef vector<ll> vl;
typedef vector<vl> vvl;
 auto start = std::chrono::steady_clock::now(); // since(start).count()
    


void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    ll start = chrono::steady_clock::now().time_since_epoch().count();
    int M = U.size();
    vl invalid(N, 0);
    for (int j = 0; j < 50; ++j) {
        std::vector<int> w(M);
        for (int i = 0; i < M; ++i) {
            w[i] = rand()%2;
        }
        long long toll = ask(w);
        // deb(toll);
        queue<pair<ll, ll>> pq;
        pq.push({0, 0});
        vl seen(N, 0);
        ll cost, pos;
        vector<vector<pair<ll, ll>>> adj(N);
        fo(i, M){
            adj[U[i]].pb({V[i], (w[i]?B:A)});
            adj[V[i]].pb({U[i], (w[i]?B:A)});
        }
        while(!pq.empty()){
            tie(cost, pos) = pq.front();
            pq.pop();
            cost = -cost;
            if(seen[pos]) continue;
            // deb2(pos, cost);
            invalid[pos]|=cost!=toll;
            seen[pos] = 1;
            for(auto &[v, w] : adj[pos]){
                pq.push({-cost-w, v});
            }
        }
    }
    int ans = 0;
    fo(i, N) if(!invalid[i]) ans = i; 
    // fo(i, N) deb(invalid[i]);
    answer(0, ans);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:21:8: warning: unused variable 'start' [-Wunused-variable]
   21 |     ll start = chrono::steady_clock::now().time_since_epoch().count();
      |        ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 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 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 86 ms 1624 KB Output is correct
3 Correct 906 ms 10716 KB Output is correct
4 Correct 870 ms 10920 KB Output is correct
5 Correct 858 ms 12244 KB Output is correct
6 Correct 898 ms 10644 KB Output is correct
7 Correct 845 ms 10812 KB Output is correct
8 Correct 853 ms 10924 KB Output is correct
9 Correct 846 ms 10728 KB Output is correct
10 Correct 858 ms 10724 KB Output is correct
11 Correct 895 ms 10524 KB Output is correct
12 Correct 919 ms 10404 KB Output is correct
13 Correct 912 ms 10564 KB Output is correct
14 Correct 899 ms 10560 KB Output is correct

Subtask #3
0 / 6.0

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