oj.uz

Submission #116962

# Submission time Handle Problem Language Result Execution time Memory
116962 2019-06-14T09:01:53 Z pzdba Highway Tolls (IOI18_highway) C++14
51 / 100
 252 ms 24616 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
vector<pii> g[90005];
int depth[90005], par[90005];
vector<int> ud[90005];

void dfs(int u, int p, int j, int d){
    depth[u] = d;
    par[u] = j;
    ud[d].push_back(u);
    for(int i=0;i<g[u].size();i++){
        int v = g[u][i].first, j = g[u][i].second;
        if(v == p) continue;
        dfs(v, u, j, d+1);
    }
}
void find_pair(int n, std::vector<int> u, std::vector<int> v, int a, int b){
    int m = u.size();
    for(int i=0;i<m;i++){
        int a = u[i], b = v[i];
        g[a].push_back(pii(b, i));
        g[b].push_back(pii(a, i));
    }
    dfs(0, -1, 0, 0);
    vector<int> w;
    w.resize(m);
    LL base = ask(w);
    int lo = 1, hi = n, dd = 0, s = 0, t = 0;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        for(int i=0;i<m;i++) w[i] = 0;
        for(int j=mid;j<=n;j++){
            for(int k=0;k<ud[j].size();k++){
                int u = ud[j][k];
                w[par[u]] = 1;
            }
        }
        LL tmp = ask(w);
        if(tmp > base) lo = mid+1, dd = mid;
        else hi = mid-1;
    }
    lo = 0, hi = ud[dd].size()-1;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        for(int i=0;i<m;i++) w[i] = 0;
        for(int j=0;j<=mid;j++){
            int u = ud[dd][j];
            w[par[u]] = 1;
        }
        LL tmp = ask(w);
        if(tmp > base) hi = mid-1, s = ud[dd][mid];
        else lo = mid+1;
    }
    for(int i=0;i<=n;i++) ud[i].clear();
    dfs(s, -1, 0, 0);
    dd = base/a;
    lo = 0, hi = ud[dd].size()-1;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        for(int i=0;i<m;i++) w[i] = 0;
        for(int j=0;j<=mid;j++){
            int u = ud[dd][j];
            w[par[u]] = 1;
        }
        LL tmp = ask(w);
        if(tmp > base) hi = mid-1, t = ud[dd][mid];
        else lo = mid+1;
    }
    answer(s, t);
}

Compilation message

highway.cpp: In function 'void dfs(int, int, int, int)':
highway.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++){
                 ~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:36:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0;k<ud[j].size();k++){
                         ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4600 KB Output is correct
2 Correct 6 ms 4472 KB Output is correct
3 Correct 6 ms 4472 KB Output is correct
4 Correct 5 ms 4600 KB Output is correct
5 Correct 6 ms 4484 KB Output is correct
6 Correct 6 ms 4472 KB Output is correct
7 Correct 5 ms 4500 KB Output is correct
8 Correct 6 ms 4600 KB Output is correct
9 Correct 6 ms 4520 KB Output is correct
10 Correct 6 ms 4600 KB Output is correct
11 Correct 6 ms 4604 KB Output is correct
12 Correct 6 ms 4472 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4600 KB Output is correct
2 Correct 28 ms 5252 KB Output is correct
3 Correct 209 ms 11040 KB Output is correct
4 Correct 231 ms 11008 KB Output is correct
5 Correct 211 ms 11108 KB Output is correct
6 Correct 221 ms 11124 KB Output is correct
7 Correct 223 ms 11304 KB Output is correct
8 Correct 204 ms 11304 KB Output is correct
9 Correct 241 ms 11352 KB Output is correct
10 Correct 235 ms 11024 KB Output is correct
11 Correct 234 ms 11828 KB Output is correct
12 Correct 241 ms 12864 KB Output is correct
13 Correct 232 ms 11896 KB Output is correct
14 Correct 218 ms 12236 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5800 KB Output is correct
2 Correct 45 ms 7288 KB Output is correct
3 Correct 60 ms 8624 KB Output is correct
4 Correct 150 ms 16876 KB Output is correct
5 Correct 182 ms 16980 KB Output is correct
6 Correct 178 ms 17124 KB Output is correct
7 Correct 178 ms 16876 KB Output is correct
8 Correct 172 ms 16880 KB Output is correct
9 Correct 173 ms 16888 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4636 KB Output is correct
2 Correct 27 ms 5272 KB Output is correct
3 Correct 144 ms 9740 KB Output is correct
4 Correct 200 ms 11064 KB Output is correct
5 Correct 198 ms 10940 KB Output is correct
6 Correct 207 ms 11032 KB Output is correct
7 Correct 227 ms 11076 KB Output is correct
8 Correct 201 ms 11072 KB Output is correct
9 Correct 229 ms 10980 KB Output is correct
10 Correct 216 ms 11052 KB Output is correct
11 Correct 222 ms 11740 KB Output is correct
12 Correct 195 ms 12568 KB Output is correct
13 Correct 224 ms 12036 KB Output is correct
14 Correct 252 ms 12560 KB Output is correct
15 Correct 214 ms 10980 KB Output is correct
16 Correct 191 ms 11300 KB Output is correct
17 Correct 232 ms 12288 KB Output is correct
18 Correct 240 ms 12324 KB Output is correct
19 Correct 231 ms 11184 KB Output is correct
20 Correct 238 ms 12968 KB Output is correct
21 Correct 201 ms 11180 KB Output is correct
22 Correct 222 ms 11080 KB Output is correct
23 Correct 195 ms 11048 KB Output is correct
24 Correct 247 ms 11900 KB Output is correct
25 Correct 242 ms 16304 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 24580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 24616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -