Submission #299790

#	Time	Username	Problem	Language	Result	Execution time	Memory
299790		Dremix10	Highway Tolls (IOI18_highway)	C++17	6 / 100	322 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],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){
     //   cout<<"go "<<x.F<<" "<<x.S<<endl;
        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});
     //   cout<<x<<" "<<y<<" "<<i<<endl;
    }
    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(start,start,0);

    //for(i=0;i<n;i++){
    //    cout<<d[i]<<" "<<maxi[i]<<endl;
    //}cout<<endl;
    int l = 0,r = n-2;
    reverse(all(arr));
   // for(auto x : arr)
    //    cout<<x<<" "<<par[x]<<endl;
   // cout<<endl;
    int f;
   // cout<<ini<<endl;
    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;
       // cout<<mid<<" "<<cur<<endl;
        if(cur!=ini){
            f = arr[mid];
            r = mid-1;
        }
        else
            l = mid+1;
    }
   // cout<<f<<endl;
    int s;
    reverse(all(arr));
    //for(auto x : arr)
    //    cout<<x<<" "<<go[x]<<endl;
    l = 0,r = n-2;
    while(l<=r){
        int mid = (l+r)/2;
        for(i=0;i<=mid;i++)
            q[go[arr[i]]] = 1;
        ll cur = ask(q);
        for(i=0;i<=mid;i++)
            q[go[arr[i]]] = 0;
            //cout<<mid<<" "<<cur<<endl;
        if(cur!=ini){
            s = arr[mid];
            r = mid-1;
        }
        else
            l = mid+1;
    }
    //cout<<s<<endl;
    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

    6 5 3 5 2 4
    0 1
    1 2
    2 3
    3 4
    4 5

    */

}

Compilation message (stderr)

highway.cpp: In function 'void solve(int, int)':
highway.cpp:70:19: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     solve(curr[ans].F,s);
      |                   ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:149:11: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
  149 |     answer(f,s);
      |     ~~~~~~^~~~~
highway.cpp:149:11: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:99:8: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |     dfs(start,start,0);
      |     ~~~^~~~~~~~~~~~~~~

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