oj.uz

Submission #349504

# Submission time Handle Problem Language Result Execution time Memory
349504 2021-01-17T16:58:30 Z beksultan04 Highway Tolls (IOI18_highway) C++14
51 / 100
 276 ms 12392 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 cnt = 1,h=0,ans = ask(w),dist = ans/A;
    vector <int> v;
    v.pb(0);
    vis[0]=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:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while (h < v.size()){
      |            ~~^~~~~~~~~~
highway.cpp:58:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int m  = l+r>>1,f=0;
      |                  ~^~
highway.cpp:58:25: warning: unused variable 'f' [-Wunused-variable]
   58 |         int m  = l+r>>1,f=0;
      |                         ^
highway.cpp:78:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     while (h < v.size()){
      |            ~~^~~~~~~~~~
highway.cpp:92:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |             int m  = l+r>>1,f=0;
      |                      ~^~
highway.cpp:92:29: warning: unused variable 'f' [-Wunused-variable]
   92 |             int m  = l+r>>1,f=0;
      |                             ^
highway.cpp:41:9: warning: unused variable 'cnt' [-Wunused-variable]
   41 |     int cnt = 1,h=0,ans = ask(w),dist = ans/A;
      |         ^~~
highway.cpp:41:34: warning: unused variable 'dist' [-Wunused-variable]
   41 |     int cnt = 1,h=0,ans = ask(w),dist = ans/A;
      |                                  ^~~~
highway.cpp:55:9: warning: unused variable 'aa' [-Wunused-variable]
   55 |     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 2668 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 2 ms 2668 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 2796 KB Output is correct
2 Correct 14 ms 3564 KB Output is correct
3 Correct 150 ms 10684 KB Output is correct
4 Correct 156 ms 10672 KB Output is correct
5 Correct 195 ms 10668 KB Output is correct
6 Correct 157 ms 10772 KB Output is correct
7 Correct 152 ms 10684 KB Output is correct
8 Correct 146 ms 10616 KB Output is correct
9 Correct 186 ms 10676 KB Output is correct
10 Correct 158 ms 10720 KB Output is correct
11 Correct 174 ms 10184 KB Output is correct
12 Correct 165 ms 10132 KB Output is correct
13 Correct 158 ms 10084 KB Output is correct
14 Correct 202 ms 10164 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3564 KB Output is correct
2 Correct 25 ms 4404 KB Output is correct
3 Correct 51 ms 4972 KB Output is correct
4 Correct 118 ms 10180 KB Output is correct
5 Correct 153 ms 10124 KB Output is correct
6 Correct 154 ms 10132 KB Output is correct
7 Correct 151 ms 10064 KB Output is correct
8 Correct 158 ms 10088 KB Output is correct
9 Correct 128 ms 10128 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 112 ms 9420 KB Output is correct
4 Correct 139 ms 10712 KB Output is correct
5 Correct 147 ms 10668 KB Output is correct
6 Correct 146 ms 10656 KB Output is correct
7 Correct 141 ms 10728 KB Output is correct
8 Correct 153 ms 10640 KB Output is correct
9 Correct 149 ms 10672 KB Output is correct
10 Correct 151 ms 10740 KB Output is correct
11 Correct 157 ms 10152 KB Output is correct
12 Correct 153 ms 10220 KB Output is correct
13 Correct 151 ms 10176 KB Output is correct
14 Correct 208 ms 10072 KB Output is correct
15 Correct 170 ms 10716 KB Output is correct
16 Correct 150 ms 10716 KB Output is correct
17 Correct 199 ms 10144 KB Output is correct
18 Correct 163 ms 10116 KB Output is correct
19 Correct 187 ms 10708 KB Output is correct
20 Correct 158 ms 10084 KB Output is correct
21 Correct 163 ms 10784 KB Output is correct
22 Correct 125 ms 10888 KB Output is correct
23 Correct 134 ms 10840 KB Output is correct
24 Correct 133 ms 10708 KB Output is correct
25 Correct 148 ms 10244 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3820 KB Output is correct
2 Correct 24 ms 3692 KB Output is correct
3 Correct 208 ms 11044 KB Output is correct
4 Correct 188 ms 11604 KB Output is correct
5 Correct 276 ms 12392 KB Output is correct
6 Incorrect 204 ms 12360 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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