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

highway

#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;
      |         ^~~

Subtask #1
0 / 5.0

#	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	-

Subtask #2
0 / 7.0

#	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	-

Subtask #3
6.0 / 6.0

#	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