Submission #433073

#	Time	Username	Problem	Language	Result	Execution time	Memory
433073		HediChehaidar	Highway Tolls (IOI18_highway)	C++17	5 / 100	291 ms	18936 KiB

highway

/*
ID: hedichehaidar
TASK: photo
LANG: C++11
*/
#include<bits/stdc++.h>
#include "highway.h"
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define dte  tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = INF + 7;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;

ll a , b , n ,m ;
vi adj[(int)1e5];
map<pii , int> e;
int cur = 0 , len;
/*void answer(int x , int y){
    cout << x << " " << y << "\n";
}
ll ask(vi v){
    for(auto c : v) cout << c << " " ; cout << endl;
    ll c ; cin>>c;
    return c;
}*/
vi v;
void find_pair(int N, vi U, vi V, int A, int B){
    n = N; m = U.size();
    if(n != m + 1){
        answer(0 , 1);
        return;
    }
    a = A; b = B;
    for(int i = 0 ; i < m ; i++){
        int d = U[i] , f = V[i];
        adj[d].pb(f);
        adj[f].pb(d);
        e[{d, f}]  = i;
        e[{f, d}]  = i;
    }
    v.assign(m , 0);
    ll res = ask(v);
    len = res / a;
    int last = -1;
    while(len){
        int l = 0 , r = adj[cur].size() - 1;
        while(l < r){
            vi edges(m , 0);
            int mid = (l+r) / 2;
            //cout <<cur << " " <<last << " "<<  l << " " << r << " " << mid << endl;
            if(r - l == 1) {
                if(last != -1){
                    if(adj[cur][l] == last){
                        l = r; break;
                    }
                    if(adj[cur][r] == last) break;
                }
                edges[e[{cur , adj[cur][l]}]] = 1;
                ll x = ask(edges);
                if(x == res) l = r;
                break;
            }
            for(int i = l ; i <= mid ; i++) edges[e[{cur , adj[cur][i]}]] = 1;
            if(last != -1) edges[e[{cur , last}]] = 0;
            ll x = ask(edges);
            if(x > res) {
                r = mid;
            }
            else l = mid + 1;
        }
        last = cur;
        cur = adj[cur][l]; len--;
    }
    answer(0 , cur);
}
/*int main(){
    //ifstream fin ("race.in");
    //ofstream fout ("race.out");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int N , M , A , B; cin>>N>>M>>A>>B;
    vi U(M) , V(M);
    for(int i = 0 ; i < M ; i++) cin>>U[i]>>V[i];
    find_pair(N , U, V , A , B);
    return 0;
}*/
/*
19
18
1 2
0 1
1 2
2 3
1 4
1 5
5 6
5 7
1 8
1 13
13 12
13 11
13 9
13 10
2 14
14 15
14 16
14 17
14 18
*/
/*
    Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO
    Read the statement CAREFULLY !!
    Make a GREADY APPROACH !!!! (start from highest / lowest)
    Make your own TESTS !!
    Be careful from CORNER CASES !
*/

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