Submission #299777

#	Time	Username	Problem	Language	Result	Execution time	Memory
299777		Dremix10	Highway Tolls (IOI18_highway)	C++17	12 / 100	286 ms	262148 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];

void dfs(int s, int e, int road){
    maxi[s] = d[s];
    par[s] = e;
    if(d[s]==dep){
        ans.push_back({s,road});
    }
    for(auto x : a[s])
    if(x.F!=e){
        d[x.F] = d[s]+1;
        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;
    dfs(0,0,0);
    //for(i=0;i<n;i++){
    //    cout<<d[i]<<" "<<maxi[i]<<endl;
    //}cout<<endl;

    assert(!ans.empty());
    int l = 0,r = ans.size()-1;
    int out;

    while(l<=r){
        int mid = (l+r)/2;
        for(i=0;i<=mid;i++){
            q[ans[i].S] = 1;
        }
        ll now = ask(q);
        for(i=0;i<=mid;i++){
            q[ans[i].S] = 0;
        }
        if(now!=ini){
            r = mid-1;
            out = mid;
        }
        else
            l = mid+1;
    }
    answer(0,ans[out].F);
    /*

    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 solve(int, int)':
highway.cpp:66:19: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |     solve(curr[ans].F,s);
      |                   ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:115:21: warning: 'out' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |     answer(0,ans[out].F);
      |                     ^

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