oj.uz

Submission #170216

# Submission time Handle Problem Language Result Execution time Memory
170216 2019-12-24T09:05:32 Z alexandra_udristoiu Highway Tolls (IOI18_highway) C++14
100 / 100
 360 ms 13224 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include "highway.h"
#define f first
#define s second
#define DIM 130005
using namespace std;
static int t[2][DIM], niv[2][DIM], viz[2][DIM], m, p[2][DIM], nr[2], n, cd[DIM];
static pair<int, int> w[DIM], aux[DIM];
static vector<int> r, v[DIM];
void bfs(int i, int srs){
   int st, dr, j, nod, vecin;
   viz[i][srs] = 1;
   cd[1] = srs;
   st = dr = 1;
   while(st <= dr){
        nod = cd[st];
        st++;
        for(j = 0; j < v[nod].size(); j++){
            vecin = v[nod][j];
            if(viz[i][vecin] == 0){
                cd[++dr] = vecin;
                niv[i][vecin] = 1 + niv[i][nod];
                t[i][vecin] = nod;
                viz[i][vecin] = 1;
            }
        }
   }
}
int solve(int ind, long long sum){
    int i, st, dr, mid, nr;
    nr = 0;
    for(i = 1; i <= n; i++){
        if(niv[ind][i] < niv[1 - ind][i]){
            aux[++nr] = make_pair(niv[ind][i], i);
        }
    }
    sort(aux + 1, aux + nr + 1);
    for(i = 1; i <= nr; i++){
        p[ind][ aux[i].s ] = i;
    }
    st = 1;
    dr = nr;
    while(st <= dr){
        mid = (st + dr) / 2;
        for(i = 0; i < m; i++){
            r[i] = 0;
            if(p[ind][ w[i].f ] > mid || p[ind][ w[i].s ] > mid){
                r[i] = 1;
            }
        }
        if(ask(r) == sum){
            dr = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }
    return aux[st].s;
}
void find_pair(int N, vector<int> U, vector<int> V, int a, int b){
    n = N;
    int i, st, dr, mid, x, y;
    long long sum, cost;
    m = U.size();
    r.resize(m);
    for(i = 0; i < m; i++){
        w[i] = make_pair(U[i] + 1, V[i] + 1);
        v[ w[i].f ].push_back(w[i].s);
        v[ w[i].s ].push_back(w[i].f);
        r[i] = 0;
    }
    sum = ask(r);
    st = 1;
    dr = m;
    while(st <= dr){
        mid = (st + dr) / 2;
        for(i = 0; i < m; i++){
            if(i < mid){
                r[i] = 0;
            }
            else{
                r[i] = 1;
            }
        }
        if(ask(r) == sum){
            dr = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }
    bfs(0, w[dr].f);
    bfs(1, w[dr].s);
    x = solve(0, sum);
    y = solve(1, sum);
    answer(x - 1, y - 1);
}

Compilation message

highway.cpp: In function 'void bfs(int, int)':
highway.cpp:20:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j = 0; j < v[nod].size(); j++){
                    ~~^~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:65:20: warning: unused variable 'cost' [-Wunused-variable]
     long long sum, cost;
                    ^~~~
highway.cpp: At global scope:
highway.cpp:9:63: warning: 'nr' defined but not used [-Wunused-variable]
 static int t[2][DIM], niv[2][DIM], viz[2][DIM], m, p[2][DIM], nr[2], n, cd[DIM];
                                                               ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3404 KB Output is correct
3 Correct 5 ms 3320 KB Output is correct
4 Correct 5 ms 3612 KB Output is correct
5 Correct 4 ms 3396 KB Output is correct
6 Correct 5 ms 3320 KB Output is correct
7 Correct 5 ms 3320 KB Output is correct
8 Correct 5 ms 3320 KB Output is correct
9 Correct 5 ms 3320 KB Output is correct
10 Correct 5 ms 3448 KB Output is correct
11 Correct 5 ms 3452 KB Output is correct
12 Correct 5 ms 3448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3448 KB Output is correct
2 Correct 27 ms 4344 KB Output is correct
3 Correct 249 ms 11888 KB Output is correct
4 Correct 237 ms 12016 KB Output is correct
5 Correct 226 ms 11628 KB Output is correct
6 Correct 216 ms 11732 KB Output is correct
7 Correct 219 ms 11900 KB Output is correct
8 Correct 230 ms 12068 KB Output is correct
9 Correct 230 ms 11884 KB Output is correct
10 Correct 245 ms 11900 KB Output is correct
11 Correct 310 ms 11656 KB Output is correct
12 Correct 243 ms 11852 KB Output is correct
13 Correct 300 ms 11844 KB Output is correct
14 Correct 265 ms 11960 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4264 KB Output is correct
2 Correct 44 ms 5056 KB Output is correct
3 Correct 61 ms 6008 KB Output is correct
4 Correct 180 ms 11248 KB Output is correct
5 Correct 177 ms 11264 KB Output is correct
6 Correct 171 ms 11520 KB Output is correct
7 Correct 173 ms 11492 KB Output is correct
8 Correct 172 ms 11288 KB Output is correct
9 Correct 173 ms 11372 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3448 KB Output is correct
2 Correct 26 ms 4344 KB Output is correct
3 Correct 166 ms 10008 KB Output is correct
4 Correct 221 ms 12024 KB Output is correct
5 Correct 219 ms 11892 KB Output is correct
6 Correct 202 ms 11640 KB Output is correct
7 Correct 216 ms 11648 KB Output is correct
8 Correct 236 ms 11628 KB Output is correct
9 Correct 249 ms 11744 KB Output is correct
10 Correct 231 ms 11664 KB Output is correct
11 Correct 265 ms 11940 KB Output is correct
12 Correct 249 ms 11864 KB Output is correct
13 Correct 259 ms 11796 KB Output is correct
14 Correct 244 ms 11776 KB Output is correct
15 Correct 222 ms 11784 KB Output is correct
16 Correct 241 ms 11808 KB Output is correct
17 Correct 290 ms 11872 KB Output is correct
18 Correct 235 ms 11960 KB Output is correct
19 Correct 226 ms 11628 KB Output is correct
20 Correct 243 ms 11832 KB Output is correct
21 Correct 212 ms 11904 KB Output is correct
22 Correct 198 ms 12024 KB Output is correct
23 Correct 237 ms 11900 KB Output is correct
24 Correct 255 ms 11872 KB Output is correct
25 Correct 253 ms 11936 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4356 KB Output is correct
2 Correct 33 ms 4392 KB Output is correct
3 Correct 270 ms 11988 KB Output is correct
4 Correct 286 ms 12268 KB Output is correct
5 Correct 340 ms 12980 KB Output is correct
6 Correct 322 ms 13208 KB Output is correct
7 Correct 335 ms 13004 KB Output is correct
8 Correct 350 ms 12940 KB Output is correct
9 Correct 264 ms 9868 KB Output is correct
10 Correct 248 ms 9976 KB Output is correct
11 Correct 225 ms 10340 KB Output is correct
12 Correct 333 ms 11940 KB Output is correct
13 Correct 319 ms 12528 KB Output is correct
14 Correct 331 ms 12888 KB Output is correct
15 Correct 315 ms 12928 KB Output is correct
16 Correct 285 ms 10560 KB Output is correct
17 Correct 198 ms 12312 KB Output is correct
18 Correct 231 ms 12440 KB Output is correct
19 Correct 234 ms 12316 KB Output is correct
20 Correct 208 ms 12532 KB Output is correct
21 Correct 328 ms 13136 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4256 KB Output is correct
2 Correct 27 ms 4264 KB Output is correct
3 Correct 259 ms 11976 KB Output is correct
4 Correct 283 ms 12208 KB Output is correct
5 Correct 290 ms 12440 KB Output is correct
6 Correct 293 ms 13224 KB Output is correct
7 Correct 251 ms 12096 KB Output is correct
8 Correct 263 ms 12048 KB Output is correct
9 Correct 246 ms 12324 KB Output is correct
10 Correct 328 ms 13124 KB Output is correct
11 Correct 305 ms 12876 KB Output is correct
12 Correct 360 ms 13184 KB Output is correct
13 Correct 260 ms 10352 KB Output is correct
14 Correct 271 ms 9832 KB Output is correct
15 Correct 273 ms 10244 KB Output is correct
16 Correct 242 ms 9928 KB Output is correct
17 Correct 266 ms 10268 KB Output is correct
18 Correct 278 ms 9820 KB Output is correct
19 Correct 311 ms 11944 KB Output is correct
20 Correct 294 ms 12380 KB Output is correct
21 Correct 346 ms 12792 KB Output is correct
22 Correct 315 ms 12732 KB Output is correct
23 Correct 351 ms 12720 KB Output is correct
24 Correct 320 ms 13032 KB Output is correct
25 Correct 338 ms 12892 KB Output is correct
26 Correct 343 ms 12984 KB Output is correct
27 Correct 218 ms 12048 KB Output is correct
28 Correct 214 ms 12296 KB Output is correct
29 Correct 256 ms 12500 KB Output is correct
30 Correct 237 ms 12376 KB Output is correct
31 Correct 229 ms 12344 KB Output is correct
32 Correct 226 ms 12320 KB Output is correct
33 Correct 233 ms 12516 KB Output is correct
34 Correct 228 ms 12372 KB Output is correct
35 Correct 229 ms 11952 KB Output is correct
36 Correct 235 ms 12248 KB Output is correct
37 Correct 235 ms 12632 KB Output is correct
38 Correct 231 ms 12180 KB Output is correct
39 Correct 330 ms 13076 KB Output is correct
40 Correct 335 ms 13160 KB Output is correct
41 Correct 316 ms 13096 KB Output is correct
42 Correct 344 ms 12972 KB Output is correct