Submission #349508

#	Time	Username	Problem	Language	Result	Execution time	Memory
349508		beksultan04	Highway Tolls (IOI18_highway)	C++14	51 / 100	205 ms	10936 KiB

highway

#include "highway.h"
#ifndef EVAL
#include "grader.cpp"
#endif // EVAL
#include <bits/stdc++.h>
using namespace std;
#define lol long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scanl(a) scanf("%lld",&a);
#define scanll(a,b) scanf("%lld %lld",&a, &b);
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define scan1(a) scanf("%d",&a);
#define scan2(a,b) scanf("%d %d",&a, &b);
#define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
#define eps 1e-12
const int NN = 1e5+12,INF=1e9+7;
bool vis[NN],may[NN];
vector <pii> g[NN];
int cost[NN];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int m = U.size(),i;
    vector <int> w;
    vector <pii> q,e;
    for (i=0;i<m;++i){
        w.pb(0);
        g[U[i]].pb({V[i],i});
        g[V[i]].pb({U[i],i});
    }
    int star,cnt = 1,h=0,ans = ask(w),dist = ans/A;
    {
        int l = 0,r = m-1;
        while (r-l>0){

            int m  = l+r>>1;
            for (i=m+1;i<=r;++i){
                w[U[i]] = 1;
            }


            int asd = ask(w);
            if (asd != ans){
                l = m+1;
            }
            else {
                r = m;
            }


            for (i=m+1;i<=r;++i){
                w[U[i]] = 0;
            }


        }
        star = U[l];
    }

    vector <int> v;
    v.pb(star);
    vis[star]=1;
    while (h < v.size()){
        int x = v[h++];
        for (auto to: g[x]){
            if (vis[to.fr] == 0){
                q.pb({to.sc,to.fr});
                vis[to.fr] = 1;
                v.pb(to.fr);
            }
        }
    }v.clear();
    int aa = ans;
    int l = 0, r = q.size()-1;
    while (r - l > 0){
        int m  = l+r>>1,f=0;
        for (i=m+1;i<=r;++i){
            w[q[i].fr] = 1;
        }
        int asd = ask(w);
        if (asd != ans){
            l = m+1;
        }
        else {
            r = m;
        }
        for (i=m;i<=r;++i){
            w[q[i].fr] = 0;
        }
    }
    int s = q[l].sc;
    for (i=0;i<N;++i)vis[i]=0;
    v.pb(s);
    vis[s]=1;
    h=0;
    while (h < v.size()){
        int x = v[h++];
        for (auto to: g[x]){
            if (vis[to.fr] == 0){
                e.pb({to.sc,to.fr});
                vis[to.fr] = 1;
                v.pb(to.fr);
            }
        }
    }
    int t;
    {
        int l = 0, r = e.size()-1;
        while (r - l > 0){
            int m  = l+r>>1,f=0;
            for (i=m+1;i<=r;++i){
                w[e[i].fr] = 1;
            }
            int asd = ask(w);
            if (asd != ans){
                l = m+1;
            }
            else {
                r = m;
            }
            for (i=m;i<=r;++i){
                w[e[i].fr] = 0;
            }
        }
        t = e[l].sc;
    }
    answer(s,t);



}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:46:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |             int m  = l+r>>1;
      |                      ~^~
highway.cpp:73:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     while (h < v.size()){
      |            ~~^~~~~~~~~~
highway.cpp:86:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int m  = l+r>>1,f=0;
      |                  ~^~
highway.cpp:86:25: warning: unused variable 'f' [-Wunused-variable]
   86 |         int m  = l+r>>1,f=0;
      |                         ^
highway.cpp:106:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     while (h < v.size()){
      |            ~~^~~~~~~~~~
highway.cpp:120:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |             int m  = l+r>>1,f=0;
      |                      ~^~
highway.cpp:120:29: warning: unused variable 'f' [-Wunused-variable]
  120 |             int m  = l+r>>1,f=0;
      |                             ^
highway.cpp:41:14: warning: unused variable 'cnt' [-Wunused-variable]
   41 |     int star,cnt = 1,h=0,ans = ask(w),dist = ans/A;
      |              ^~~
highway.cpp:41:39: warning: unused variable 'dist' [-Wunused-variable]
   41 |     int star,cnt = 1,h=0,ans = ask(w),dist = ans/A;
      |                                       ^~~~
highway.cpp:83:9: warning: unused variable 'aa' [-Wunused-variable]
   83 |     int aa = ans;
      |         ^~

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