Submission #823261

# Submission time Handle Problem Language Result Execution time Memory
823261 2023-08-12T10:09:25 Z Dremix10 Highway Tolls (IOI18_highway) C++17
6 / 100
101 ms 14348 KB
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 3e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;

vector<vector<pi> > a(N);
vector<pi> pos;
vector<pi> par(N);

void dfs(int s, int e, int cur, int f){
    if(cur == f){
        pos.push_back({par[s].S,s});
        return;
    }
    for(auto x : a[s]){
        if(x.F == e)continue;
        par[x.F] = {s,x.S};
        dfs(x.F,s,cur+1,f);
    }
}

void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
    int i;

    int m = u.size();

    for(i=0;i<m;i++){
        a[v[i]].push_back({u[i],i});
        a[u[i]].push_back({v[i],i});
    }

    vector<int> w(m,0);

    ll d = ask(w);
    int dep = d/A;

    int l = 0,r = n-2;

    while(l < r){
        int mid = (l+r)/2;
        for(i=0;i<=mid;i++){
            w[i] = 1;
        }
        ll res = ask(w);
        for(i=0;i<=mid;i++){
            w[i] = 0;
        }

        if(res != d){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }

    int S = r;

    l = 1,r = n-1;

    while(l < r){
        int mid = (l+r+1)/2;
        for(i=n-1;i>=mid;i--){
            w[i-1] = 1;
        }
        ll res = ask(w);
        for(i=n-1;i>=mid;i--){
            w[i-1] = 0;
        }

        if(res != d){
            l = mid;
        }
        else{
            r = mid-1;
        }
    }

    int E = l;
    cerr<<S<<" "<<E<<endl;
    answer(S,E);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:43:9: warning: unused variable 'dep' [-Wunused-variable]
   43 |     int dep = d/A;
      |         ^~~
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9680 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9680 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 10216 KB Output is correct
2 Correct 55 ms 10708 KB Output is correct
3 Correct 38 ms 11216 KB Output is correct
4 Correct 101 ms 14268 KB Output is correct
5 Correct 61 ms 14268 KB Output is correct
6 Correct 67 ms 14348 KB Output is correct
7 Correct 69 ms 14268 KB Output is correct
8 Correct 73 ms 14272 KB Output is correct
9 Correct 67 ms 14268 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9680 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 10312 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 10292 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -