Submission #299782

#	Time	Username	Problem	Language	Result	Execution time	Memory
299782		Dremix10	Highway Tolls (IOI18_highway)	C++17	0 / 100	17 ms	6400 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
const ll INF = 1e18;
const int N = 3e5+1;

vector<vector<pi> > a(100000);
vector<pi> ans;
int d[100000],dep,maxi[100000],par[100000],go[100000];
vector<int> arr;
void dfs(int s, int e, int road){
    arr.push_back(s);
    maxi[s] = d[s];
    par[s] = road;
    if(d[s]==dep){
        ans.push_back({s,road});
    }
    for(auto x : a[s])
    if(x.F!=e){
        d[x.F] = d[s]+1;
        go[s] = x.S;
        dfs(x.F,s,x.S);
        maxi[s] = max(maxi[s],maxi[x.F]);
    }
}

vector<int> q;
ll cost[2],ini;

void solve(int s, int e){
    if(d[s]==dep){
        answer(0,s);
        return;
    }
    vector<pi> curr;
    for(auto x : a[s])
    if(x.F!=e && maxi[x.F]>=dep){
        curr.push_back(x);
    }
    //for(auto x : curr)
    //    cout<<x.F<<" "<<x.S<<endl;

    assert(!curr.empty());
    int l = 0,r = curr.size()-1;
    int ans,i;
    while(l<=r){
        int mid = (l+r)/2;
        for(i=0;i<=mid;i++){
            q[curr[i].S] = 1;
        }
        ll now = ask(q);
        for(i=0;i<=mid;i++){
            q[curr[i].S] = 0;
        }
        if(now!=ini){
            r = mid-1;
            ans = mid;
        }
        else
            l = mid+1;
    }
    solve(curr[ans].F,s);
}

void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
    int m = u.size();
    int i;
    cost[0] = A;
    cost[1] = B;

    for(i=0;i<m;i++){
        int x = v[i];
        int y = u[i];
        a[x].push_back({y,i});
        a[y].push_back({x,i});
    }
    q.assign(m,0);
    ll tot = ask(q);


    dep = tot/A;
    //p2(tot,dep)
    //cout<<tot<<" "<<dep<<endl;
    //cout<<endl;
    ini = tot;
    int start;
    for(i=0;i<n;i++)
        if(a[i].size()==1)start = i;
    dfs(i,i,0);
    //for(i=0;i<n;i++){
    //    cout<<d[i]<<" "<<maxi[i]<<endl;
    //}cout<<endl;
    int l = 0,r = n-2;
    reverse(all(arr));
    int f;
    while(l<=r){
        int mid = (l+r)/2;
        for(i=0;i<=mid;i++)
            q[par[arr[i]]] = 1;
        ll cur = ask(q);
        for(i=0;i<=mid;i++)
            q[par[arr[i]]] = 0;
        if(cur!=ini){
            f = arr[mid];
            r = mid-1;
        }
        else
            l = mid+1;
    }
    int s;
    reverse(all(arr));
    l = 0,r = n-2;
    while(l<=r){
        int mid = (l+r)/2;
        for(i=0;i<=mid;i++)
            q[par[arr[i]]] = 1;
        ll cur = ask(q);
        for(i=0;i<=mid;i++)
            q[par[arr[i]]] = 0;
        if(cur!=ini){
            s = arr[mid];
            r = mid-1;
        }
        else
            l = mid+1;
    }
    answer(f,s);

    /*

    16 15 3 5 0 14
    0 1
    0 2
    0 3
    1 4
    1 5
    4 6
    4 7
    2 8
    8 9
    9 10
    3 11
    3 12
    11 14
    11 15
    12 13


    */

}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:92:9: warning: variable 'start' set but not used [-Wunused-but-set-variable]
   92 |     int start;
      |         ^~~~~
highway.cpp: In function 'void solve(int, int)':
highway.cpp:68:19: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |     solve(curr[ans].F,s);
      |                   ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:133:11: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |     answer(f,s);
      |     ~~~~~~^~~~~
highway.cpp:133:11: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31