oj.uz

Submission #1078073

# Submission time Handle Problem Language Result Execution time Memory
1078073 2024-08-27T12:14:30 Z wood Highway Tolls (IOI18_highway) C++17
5 / 100
 91 ms 16588 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

int getstart(int u, int v, vp32 adj[], int n, int depth, ll cost){
    int d[n]; memset(d,0,sizeof d);
    d[v] = INT_MAX;
    d[u] = 1;
    queue<int> q; q.push(u);
    int edge[n];
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(p32 ii : adj[x]){
            if(!d[ii.fi]){
                d[ii.fi] = d[x]+1;
                q.push(ii.fi);
                edge[ii.fi] = ii.se;
            }
        }
    }
    vi possible;
    for(int i = 0; i<n; i++){
        if(d[i]==depth+1) possible.pb(i);
    }
    int l = -1, r = possible.size()-1;
    while(r-l>1){
        int m = (r+l)/2;
        vi w(n-1);
        for(int i = l+1; i<=m; i++) w[edge[possible[i]]] = 1;
        if(ask(w)>cost) r = m;
        else l = m;
    }
    return possible[r];
}

int setsubtree(int u, int v, vp32 adj[], int n){
    bool done[n]; memset(done,0,sizeof done);
    done[v] = true;
    stack<int> st;
    st.push(u);
    vi w(n-1);
    while(!st.empty()){
        int x = st.top();
        st.pop();
        done[x] = true;
        for(auto ii : adj[x]){
            if(!done[ii.fi]){
                w[ii.se] = 1;
                st.push(ii.fi);
            }
        }
    }
    return ask(w);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int m = U.size(),n = N;
    vp32 adj[n];
    for(int i = 0; i<m; i++){
        adj[U[i]].eb(V[i],i);
        adj[V[i]].eb(U[i],i);
    }
    int l = -1, r = n;
    ll cost = ask(vi(m));
    while(r-l>1){
        int mid = (r + l) / 2;
        vi w(m);
        for(int i = l+1; i <= mid; i++)w[i] = 1;
        if(ask(w)==cost) l = mid;
        else r = mid;
    }
    int ulength = (setsubtree(U[r],V[r],adj,n)-cost)/(B-A);
    int vlength = cost/A-ulength-1;
    answer(getstart(U[r],V[r],adj,n,ulength,cost),getstart(V[r],U[r],adj,n,vlength,cost));
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 9 ms 1284 KB Output is correct
3 Correct 81 ms 8416 KB Output is correct
4 Correct 76 ms 8672 KB Output is correct
5 Correct 73 ms 8428 KB Output is correct
6 Correct 71 ms 8432 KB Output is correct
7 Correct 77 ms 8428 KB Output is correct
8 Correct 91 ms 8412 KB Output is correct
9 Correct 77 ms 8428 KB Output is correct
10 Correct 75 ms 8420 KB Output is correct
11 Correct 72 ms 7640 KB Output is correct
12 Correct 85 ms 7628 KB Output is correct
13 Correct 68 ms 7624 KB Output is correct
14 Runtime error 73 ms 15404 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1112 KB Output is correct
2 Correct 14 ms 2120 KB Output is correct
3 Correct 20 ms 2892 KB Output is correct
4 Correct 61 ms 7664 KB Output is correct
5 Correct 73 ms 7644 KB Output is correct
6 Correct 58 ms 7720 KB Output is correct
7 Correct 62 ms 7624 KB Output is correct
8 Correct 62 ms 7660 KB Output is correct
9 Runtime error 72 ms 15316 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 1236 KB Output is correct
3 Correct 52 ms 6444 KB Output is correct
4 Correct 69 ms 8432 KB Output is correct
5 Correct 64 ms 8148 KB Output is correct
6 Correct 75 ms 8204 KB Output is correct
7 Correct 86 ms 8160 KB Output is correct
8 Correct 75 ms 8160 KB Output is correct
9 Runtime error 72 ms 16588 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2136 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 2136 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -