oj.uz

Submission #891670

# Submission time Handle Problem Language Result Execution time Memory
891670 2023-12-23T14:28:27 Z vjudge1 Highway Tolls (IOI18_highway) C++17
11 / 100
 1500 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
vector<ii> E;

struct tree {
    int n;
    vi par, par_cent, sz;
    vector<vi> L, G;
    
    tree(int N) : n(N), L(N), par(N), par_cent(N), sz(N), G(N) {}

    void add_edge(int u, int v) {
        L[u].push_back(v);
        L[v].push_back(u);
    }

    void init() {
        vi on(n, 1);
        function<void(int, int)> dfs_sz = [&](int u, int p) {
            sz[u] = 1;
            for(auto it : L[u]) {
                if(on[it] && it != p) {
                    dfs_sz(it, u);
                    sz[u] += sz[it];
                }
            }
        };

        function<int(int, int, int)> find_c = [&](int u, int p, int slim) {
            for(auto it : L[u])
                if(on[it] && it != p && 2 * sz[it] > slim) return find_c(it, u, slim);
            return u;
        };

        function<void(int, int) > dfs_cent = [&](int u, int pc) {
            dfs_sz(u, -1);
            int c = find_c(u, -1, sz[u]);
            on[c] = 0;
            par_cent[c] = pc;
            if(pc != -1) {
                G[pc].push_back(c);
            }
            for(auto it : L[c])
                if(on[it]) dfs_cent(it, c);
        };

        dfs_cent(0, -1);
    }

    void solve() {
        function<void(int, int, vi&)> dfs_comp = [&](int u, int p, vi& V) {
            V.push_back(u);
            for(auto it : G[u])
                dfs_comp(it, u, V);
        };
        int cost_baza = ask(vi(E.size(), 0));
        auto dif = [&](int u, vector<vi>& Fii, int st, int dr) {
            set<int> S = {u};
            for(int i = st; i <= dr; ++i)
                for(auto it : Fii[i]) S.insert(it);
            vi w;
            for(auto [u, v] : E) {
                if(S.count(u) + S.count(v))
                    w.push_back(1);
                else
                    w.push_back(0); 
            }
            return ask(w) - cost_baza;
        };
        vi capete;
        function<void(int, int, int)> dfs_solve = [&](int c, int pc, int nr) {
            vector<vi> comp_fii;
            for(auto it : G[c]) {
                comp_fii.push_back(vi());
                dfs_comp(it, c, comp_fii.back());
            }
            int pst = -1, pdr = comp_fii.size(), nrfii = comp_fii.size();

            int v = dif(c, comp_fii, 0, nrfii - 1);
            if(!v) {
                if(nr == 1) { // v e unul dintre s & t 
                    capete.push_back(v);
                    return;
                } else {
                    ///uhhh, wtf?
                    assert(0);
                }
            }
            for(int step = 31 - __builtin_clz(nrfii); step >= 0; --step) {
                if(pst + (1 << step) < nrfii) {
                    if(!dif(c, comp_fii, 0, pst + (1 << step)))
                        pst += (1 << step);
                }
                if(pdr - (1 << step) >= 0) {
                    if(!dif(c, comp_fii, pdr - (1 << step), nrfii - 1))
                        pdr -= (1 << step);
                }
            }
            ++pst;
            --pdr;

        };
        assert(capete.size() == 2);
    }

    int cine(int rad) {
        vi niv(n);
        function<void(int, int, int)> dfs = [&](int u, int p, int li) {
            niv[u] = li;
            for(auto it : L[u]) {
                if(it != p) {
                    dfs(it, u, li + 1);
                }
            }
        };
        vi re;
        for(int i = 0; i < n; ++i) {
            re.push_back(i);
        }
        dfs(rad, -1, 0);
        sort(re.begin(), re.end(), [&](int a, int b) { return niv[a] < niv[b]; });
        int st = 0, dr = n - 1, mij;
        int q0 = 0;
        auto query = [&](int p) {
            set<int> I;
            for(int i = 0; i <= p; ++i)
                I.insert(re[i]);
            vi w;
            for(auto [u, v] : E) {
                if(I.count(u) && I.count(v)) w.push_back(1);
                else w.push_back(0);
            }
            int v = ask(w) - q0;
          //  cout << "query( " << p << ") este " << v << "\n";
            return v + q0;
        };
        q0 = query(dr);
      //  cout << "ord: ";
      //  for(auto it : re)
      //      cout << it << " ";
      //          cout << "\n";
        int cm = query(dr);
        while(st < dr) {
            mij = (st + dr) / 2;
            if(query(mij) == q0) {
                dr = mij;
            } else 
                st = mij + 1;
        }
        return re[st];
    }
};

void find_pair(int N, vi U, vi V, int A, int B) {
    tree T(N);
    for(int i = 0; i < U.size(); ++i) {
        T.add_edge(U[i], V[i]);
        E.push_back({U[i], V[i]});
    }
    T.init();
    int s = T.cine(0);
    int t = T.cine(s);
    answer(s, t);
}

Compilation message

highway.cpp: In constructor 'tree::tree(int)':
highway.cpp:13:16: warning: 'tree::L' will be initialized after [-Wreorder]
   13 |     vector<vi> L, G;
      |                ^
highway.cpp:12:8: warning:   'vi tree::par' [-Wreorder]
   12 |     vi par, par_cent, sz;
      |        ^~~
highway.cpp:15:5: warning:   when initialized here [-Wreorder]
   15 |     tree(int N) : n(N), L(N), par(N), par_cent(N), sz(N), G(N) {}
      |     ^~~~
highway.cpp: In member function 'int tree::cine(int)':
highway.cpp:147:13: warning: unused variable 'cm' [-Wunused-variable]
  147 |         int cm = query(dr);
      |             ^~
highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:161:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for(int i = 0; i < U.size(); ++i) {
      |                    ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 628 KB Output is correct
2 Correct 46 ms 2404 KB Output is correct
3 Correct 1228 ms 19012 KB Output is correct
4 Execution timed out 1572 ms 18384 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3496 KB Output is correct
2 Correct 80 ms 6460 KB Output is correct
3 Correct 148 ms 9568 KB Output is correct
4 Correct 530 ms 27096 KB Output is correct
5 Correct 416 ms 26700 KB Output is correct
6 Correct 718 ms 27112 KB Output is correct
7 Correct 527 ms 27580 KB Output is correct
8 Correct 651 ms 26852 KB Output is correct
9 Correct 504 ms 27132 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 624 KB Output is correct
2 Correct 63 ms 2648 KB Output is correct
3 Correct 518 ms 14496 KB Output is correct
4 Correct 1103 ms 18668 KB Output is correct
5 Correct 1055 ms 18576 KB Output is correct
6 Correct 1039 ms 18340 KB Output is correct
7 Correct 1070 ms 18524 KB Output is correct
8 Correct 883 ms 18496 KB Output is correct
9 Correct 1405 ms 18256 KB Output is correct
10 Correct 1164 ms 18752 KB Output is correct
11 Correct 1464 ms 21160 KB Output is correct
12 Execution timed out 1861 ms 21612 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 195 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 189 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -