oj.uz

Submission #606486

# Submission time Handle Problem Language Result Execution time Memory
606486 2022-07-26T06:51:32 Z PiejanVDC Highway Tolls (IOI18_highway) C++17
51 / 100
 608 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN = (int)2e5+5;

long long normal;
vector<int>adj[mxN];

vector<int>x,y;

void answer(int s, int t);
long long ask(const std::vector<int> &w);

void color(int u, int c, int e = -1) {
    if(c) x.push_back(u);
    else y.push_back(u);
    for(auto z : adj[u]) if(z != e) {
        color(z, 1-c, u);
    }
}

int mxDist;
vector<int>p[mxN];
vector<int>re(mxN);

map<pair<int,int>,int>id;

void dfs(int node, int dist, int e = -1) {
    mxDist = max(mxDist, dist);
    if(e > -1) p[dist].push_back(id[{node, e}]);
    re[node] = dist;
    for(auto z : adj[node]) if(z != e) dfs(z, dist+1, node);
}

int M_;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int search_point(vector<int>points) {
    int n = (int)points.size();
    int ans = -1;
    int l = 0, r = n-1;
    while(l <= r) {
        int mid = (l+r)/2;
        vector<int>Ask(M_, 0);
        for(int i = l ; i <= mid ; i++)
            Ask[points[i]] = 1;
        long long R = ask(Ask);
        if(R != normal) {
            r = mid-1;
            ans = mid;
        } else l = mid+1;
    }
    return (ans == -1 ? ans : points[ans]);
}

void find_pair(int n, vector<int>u, vector<int>v, int a, int b) {
    const int m = (int)u.size();
    M_ = m;
    vector<int>dummy(m, 0);
    normal = ask(dummy);

    for(int i = 0 ; i < n-1 ; i++)
        id[{u[i], v[i]}] = id[{v[i], u[i]}] = i, adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);

    color(0, 0);

    int len = normal / a;

    vector<int>w = x;

    int T = 10;
    bool ok = 0;
    while(T--) {
        shuffle(w.begin(), w.end(), rng);
        int mid = (int)w.size()/2;
        vector<int>Ask(m, 0);
        for(int i = 0 ; i < mid ; i++)
            for(auto z : adj[w[i]]) Ask[id[{w[i], z}]] = 1;
        if(((ask(Ask)-normal)/(b-a))&1) {
            while(w.size() > mid)
                w.pop_back();
            ok = 1;
            break;
        }
    }
    if(!ok) {
        w = y;
        while(1) {
            shuffle(w.begin(), w.end(), rng);
            int mid = (int)w.size()/2;
            vector<int>Ask(m, 0);
            for(int i = 0 ; i < mid ; i++)
                for(auto z : adj[w[i]]) Ask[id[{w[i], z}]] = 1;
            if(((ask(Ask)-normal)/(b-a))&1) {
                while(w.size() > mid)
                    w.pop_back();
                break;
            }
        }
    }
    while(w.size() > 1) {
        int mid = w.size()/2;
        vector<int>Ask(m, 0);
        for(int i = 0 ; i < mid ; i++)
            for(auto z : adj[w[i]])
                Ask[id[{w[i], z}]] = 1;
        if(((ask(Ask)-normal)/(b-a))&1) {
            while(w.size() > mid)
                w.pop_back();
        } else {
            vector<int>tmp;
            for(int i = mid ; i < w.size() ; i++)
                tmp.push_back(w[i]);
            swap(w, tmp);  
        }
    }

    int node = w[0];
    dfs(node, 0);

    int R = search_point(p[len]);
    int P = (re[u[R]] > re[v[R]] ? u[R] : v[R]);
    answer(node, P);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:81:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |             while(w.size() > mid)
      |                   ~~~~~~~~~^~~~~
highway.cpp:96:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |                 while(w.size() > mid)
      |                       ~~~~~~~~~^~~~~
highway.cpp:109:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |             while(w.size() > mid)
      |                   ~~~~~~~~~^~~~~
highway.cpp:113:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for(int i = mid ; i < w.size() ; i++)
      |                               ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10448 KB Output is correct
2 Correct 5 ms 10448 KB Output is correct
3 Correct 6 ms 10448 KB Output is correct
4 Correct 6 ms 10496 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10500 KB Output is correct
7 Correct 6 ms 10448 KB Output is correct
8 Correct 5 ms 10448 KB Output is correct
9 Correct 6 ms 10576 KB Output is correct
10 Correct 6 ms 10448 KB Output is correct
11 Correct 6 ms 10448 KB Output is correct
12 Correct 6 ms 10448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10684 KB Output is correct
2 Correct 29 ms 12360 KB Output is correct
3 Correct 579 ms 27648 KB Output is correct
4 Correct 509 ms 27664 KB Output is correct
5 Correct 504 ms 27680 KB Output is correct
6 Correct 489 ms 27812 KB Output is correct
7 Correct 577 ms 27748 KB Output is correct
8 Correct 325 ms 27588 KB Output is correct
9 Correct 482 ms 27820 KB Output is correct
10 Correct 477 ms 27804 KB Output is correct
11 Correct 383 ms 29276 KB Output is correct
12 Correct 522 ms 30876 KB Output is correct
13 Correct 545 ms 29764 KB Output is correct
14 Correct 514 ms 28996 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 13252 KB Output is correct
2 Correct 47 ms 15744 KB Output is correct
3 Correct 79 ms 18836 KB Output is correct
4 Correct 157 ms 34292 KB Output is correct
5 Correct 370 ms 34552 KB Output is correct
6 Correct 200 ms 35252 KB Output is correct
7 Correct 376 ms 36304 KB Output is correct
8 Correct 221 ms 34656 KB Output is correct
9 Correct 162 ms 34800 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10576 KB Output is correct
2 Correct 35 ms 12336 KB Output is correct
3 Correct 394 ms 23928 KB Output is correct
4 Correct 608 ms 27568 KB Output is correct
5 Correct 586 ms 27716 KB Output is correct
6 Correct 362 ms 27676 KB Output is correct
7 Correct 397 ms 27712 KB Output is correct
8 Correct 484 ms 27668 KB Output is correct
9 Correct 308 ms 27824 KB Output is correct
10 Correct 336 ms 27688 KB Output is correct
11 Correct 349 ms 28964 KB Output is correct
12 Correct 336 ms 30984 KB Output is correct
13 Correct 346 ms 30052 KB Output is correct
14 Correct 299 ms 29996 KB Output is correct
15 Correct 416 ms 27676 KB Output is correct
16 Correct 484 ms 27832 KB Output is correct
17 Correct 348 ms 29572 KB Output is correct
18 Correct 524 ms 30388 KB Output is correct
19 Correct 305 ms 27692 KB Output is correct
20 Correct 544 ms 30872 KB Output is correct
21 Correct 281 ms 28260 KB Output is correct
22 Correct 260 ms 28152 KB Output is correct
23 Correct 462 ms 28288 KB Output is correct
24 Correct 501 ms 29112 KB Output is correct
25 Correct 354 ms 36016 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 222 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 211 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -