oj.uz

Submission #349508

# Submission time Handle Problem Language Result Execution time Memory
349508 2021-01-17T17:13:36 Z beksultan04 Highway Tolls (IOI18_highway) C++14
51 / 100
 205 ms 10936 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 17 ms 3564 KB Output is correct
3 Correct 162 ms 10656 KB Output is correct
4 Correct 154 ms 10688 KB Output is correct
5 Correct 158 ms 10656 KB Output is correct
6 Correct 156 ms 10796 KB Output is correct
7 Correct 154 ms 10620 KB Output is correct
8 Correct 153 ms 10696 KB Output is correct
9 Correct 153 ms 10640 KB Output is correct
10 Correct 154 ms 10684 KB Output is correct
11 Correct 157 ms 10168 KB Output is correct
12 Correct 155 ms 10212 KB Output is correct
13 Correct 165 ms 10052 KB Output is correct
14 Correct 153 ms 10152 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3564 KB Output is correct
2 Correct 27 ms 4392 KB Output is correct
3 Correct 40 ms 4976 KB Output is correct
4 Correct 113 ms 10072 KB Output is correct
5 Correct 114 ms 10204 KB Output is correct
6 Correct 120 ms 10152 KB Output is correct
7 Correct 121 ms 10108 KB Output is correct
8 Correct 117 ms 10300 KB Output is correct
9 Correct 120 ms 10144 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2796 KB Output is correct
2 Correct 16 ms 3564 KB Output is correct
3 Correct 110 ms 9380 KB Output is correct
4 Correct 156 ms 10708 KB Output is correct
5 Correct 155 ms 10616 KB Output is correct
6 Correct 153 ms 10616 KB Output is correct
7 Correct 157 ms 10720 KB Output is correct
8 Correct 152 ms 10692 KB Output is correct
9 Correct 153 ms 10636 KB Output is correct
10 Correct 156 ms 10784 KB Output is correct
11 Correct 161 ms 10172 KB Output is correct
12 Correct 159 ms 10212 KB Output is correct
13 Correct 172 ms 10096 KB Output is correct
14 Correct 164 ms 10164 KB Output is correct
15 Correct 189 ms 10752 KB Output is correct
16 Correct 205 ms 10680 KB Output is correct
17 Correct 195 ms 10120 KB Output is correct
18 Correct 189 ms 10176 KB Output is correct
19 Correct 194 ms 10664 KB Output is correct
20 Correct 198 ms 10124 KB Output is correct
21 Correct 142 ms 10936 KB Output is correct
22 Correct 133 ms 10808 KB Output is correct
23 Correct 176 ms 10936 KB Output is correct
24 Correct 139 ms 10760 KB Output is correct
25 Correct 171 ms 10480 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3692 KB Output is correct
2 Incorrect 22 ms 3820 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 3716 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -