oj.uz

Submission #1078074

# Submission time Handle Problem Language Result Execution time Memory
1078074 2024-08-27T12:15:50 Z wood Highway Tolls (IOI18_highway) C++17
51 / 100
 85 ms 9620 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];
}

ll 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 1 ms 344 KB Output is correct
2 Correct 1 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 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 0 ms 344 KB Output is correct
11 Correct 1 ms 436 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 9 ms 1328 KB Output is correct
3 Correct 74 ms 8416 KB Output is correct
4 Correct 85 ms 8412 KB Output is correct
5 Correct 72 ms 8528 KB Output is correct
6 Correct 66 ms 8440 KB Output is correct
7 Correct 72 ms 8412 KB Output is correct
8 Correct 71 ms 8416 KB Output is correct
9 Correct 71 ms 8656 KB Output is correct
10 Correct 68 ms 8424 KB Output is correct
11 Correct 65 ms 7640 KB Output is correct
12 Correct 68 ms 7760 KB Output is correct
13 Correct 63 ms 7636 KB Output is correct
14 Correct 69 ms 7664 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1112 KB Output is correct
2 Correct 16 ms 1928 KB Output is correct
3 Correct 20 ms 2912 KB Output is correct
4 Correct 59 ms 7660 KB Output is correct
5 Correct 61 ms 7660 KB Output is correct
6 Correct 64 ms 7640 KB Output is correct
7 Correct 66 ms 7648 KB Output is correct
8 Correct 65 ms 7628 KB Output is correct
9 Correct 54 ms 7888 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1112 KB Output is correct
3 Correct 62 ms 6444 KB Output is correct
4 Correct 63 ms 8420 KB Output is correct
5 Correct 68 ms 8412 KB Output is correct
6 Correct 67 ms 8164 KB Output is correct
7 Correct 70 ms 8480 KB Output is correct
8 Correct 65 ms 8160 KB Output is correct
9 Correct 75 ms 8528 KB Output is correct
10 Correct 76 ms 8388 KB Output is correct
11 Correct 70 ms 7632 KB Output is correct
12 Correct 69 ms 7672 KB Output is correct
13 Correct 72 ms 7668 KB Output is correct
14 Correct 70 ms 7640 KB Output is correct
15 Correct 78 ms 8164 KB Output is correct
16 Correct 69 ms 8240 KB Output is correct
17 Correct 71 ms 7820 KB Output is correct
18 Correct 68 ms 7632 KB Output is correct
19 Correct 77 ms 8400 KB Output is correct
20 Correct 64 ms 7632 KB Output is correct
21 Correct 66 ms 9360 KB Output is correct
22 Correct 67 ms 9620 KB Output is correct
23 Correct 70 ms 9244 KB Output is correct
24 Correct 74 ms 9144 KB Output is correct
25 Correct 76 ms 8288 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2132 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 11 ms 2392 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -