oj.uz

Submission #773848

# Submission time Handle Problem Language Result Execution time Memory
773848 2023-07-05T09:06:22 Z doowey Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 380348 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e6 + 10;
const int LOG = 20;

int n, k;

struct outp{
    int d1, d2, d3, d4;
};

vector<pii> qq;
vector<outp> rr;

vector<int> oo;

struct tree{
    int idx;
    vector<int> T[N];
    int root = -1;
    int tt;
    int tin[N];
    int tout[N];
    int up[LOG][N];
    void dfs(int u, int pa){
        tt ++ ;
        tin[u] = tt;
        up[0][u] = pa;
        for(int ln = 1; ln < LOG; ln ++ ){
            up[ln][u]=up[ln-1][up[ln-1][u]];
        }
        if(oo.size() < k)
            oo.push_back(u);
        for(auto x : T[u]){
            dfs(x, u);
        }
        tout[u] = tt;
    }
    void input(){
        int p;
        for(int i = 1; i <= n; i ++ ){
            cin >> p;
            if(p == -1) root = i;
            else T[p].push_back(i);
        }
        dfs(root, root);
    }
    bool is_anc(int u, int v){
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }

    int lca(int u, int v){
        if(is_anc(u, v)) return u;
        for(int ln = LOG - 1; ln >= 0 ; ln -- ){
            if(!is_anc(up[ln][u], v)) u = up[ln][u];
        }
        return up[0][u];
    }
    vector<int> lis;
    vector<int> comp;
    void make_queries(vector<int> _s){
        lis = _s;
        sort(lis.begin(), lis.end(), [&](int x, int y){return tin[x] < tin[y];});
        comp = lis;
        for(int i = 0 ;i + 1 < lis.size(); i ++ ){
            if(idx == 1)
                qq.push_back(mp(lis[i], lis[i + 1]));
            comp.push_back(lca(lis[i], lis[i + 1]));
        }
        sort(comp.begin(), comp.end(), [&](int x, int y){return tin[x] < tin[y];});
        comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    }
    vector<pii> ss[N]; // dep_v = dep_u + x.se
    int dep[N];
    void add_edge(int u, int v, int w){
        ss[u].push_back(mp(v, w));
        ss[v].push_back(mp(u, -w));
    }
    void f(int u){
        for(auto x : ss[u]){
            if(dep[x.fi] == -1){
                dep[x.fi]=dep[u]+x.se;
                f(x.fi);
            }
        }
    }
    void compute(){
        int big;
        vector<int> stek;
        for(auto x : comp){
            while(!stek.empty() && is_anc(x, stek.back())) stek.pop_back();
            stek.push_back(x);
        }
        big = stek[0];
        int di, dj;
        for(int i = 0 ; i < qq.size(); i ++ ){
            int cur = lca(qq[i].fi, qq[i].se);
            if(idx == 0){
                di = rr[i].d1;
                dj = rr[i].d2;
            }
            else{
                di = rr[i].d3;
                dj = rr[i].d4;
            }
            add_edge(cur, qq[i].fi, di);
            add_edge(cur, qq[i].se, dj);
        }
        for(auto x : comp){
            dep[x] = -1;
        }
        dep[big] = 0;
        f(big);
    }
    int get_dist(int i, int j){
        int cur = lca(i, j);
        return dep[i] + dep[j] - 2 * dep[cur];
    }
};

tree ai, bi;

int main(){
    int q, t;
    cin >> n >> k >> q >> t;
    ai.input();
    bi.input();
    ai.idx = 0;
    bi.idx = 1;
    ai.make_queries(oo);
    bi.make_queries(oo);
    for(auto x : oo) cout << x << " ";
    cout << "\n";
    fflush(stdout);
    for(auto x : qq){
        cout << "? " << x.fi << " " << x.se << "\n";
    }
    cout << "!\n";
    fflush(stdout);
    rr.resize(qq.size());
    for(int i = 0 ; i < qq.size(); i ++ ){
        cin >> rr[i].d1 >> rr[i].d2 >> rr[i].d3 >> rr[i].d4;
    }
    ai.compute();
    bi.compute();
    vector<pii> qwe;
    int u, v;
    for(int it = 1; it <= t; it ++ ){
        cin >> u >> v;
        qwe.push_back(mp(u, v));
    }
    for(auto x : qwe){
        cout << ai.get_dist(x.fi, x.se) << " " << bi.get_dist(x.fi, x.se) << "\n";
    }
    fflush(stdout);
    return 0;
}

Compilation message

Main.cpp: In member function 'void tree::dfs(int, int)':
Main.cpp:42:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |         if(oo.size() < k)
      |            ~~~~~~~~~~^~~
Main.cpp: In member function 'void tree::make_queries(std::vector<int>)':
Main.cpp:75:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i = 0 ;i + 1 < lis.size(); i ++ ){
      |                        ~~~~~~^~~~~~~~~~~~
Main.cpp: In member function 'void tree::compute()':
Main.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int i = 0 ; i < qq.size(); i ++ ){
      |                         ~~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:151:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int i = 0 ; i < qq.size(); i ++ ){
      |                     ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1612 ms 240684 KB Output is correct
2 Correct 1651 ms 244952 KB Output is correct
3 Correct 1787 ms 213216 KB Output is correct
4 Correct 1716 ms 212072 KB Output is correct
5 Correct 1843 ms 216164 KB Output is correct
6 Correct 2282 ms 221184 KB Output is correct
7 Correct 2197 ms 221100 KB Output is correct
8 Correct 2063 ms 220132 KB Output is correct
9 Correct 1797 ms 212900 KB Output is correct
10 Correct 1799 ms 215380 KB Output is correct
11 Correct 1654 ms 210624 KB Output is correct
12 Correct 1988 ms 214616 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1959 ms 244968 KB Output is correct
2 Correct 1728 ms 238980 KB Output is correct
3 Correct 2000 ms 213100 KB Output is correct
4 Correct 2162 ms 216516 KB Output is correct
5 Correct 1969 ms 214120 KB Output is correct
6 Correct 2106 ms 217720 KB Output is correct
7 Correct 2636 ms 222308 KB Output is correct
8 Correct 2436 ms 222896 KB Output is correct
9 Correct 2265 ms 220960 KB Output is correct
10 Correct 2311 ms 222220 KB Output is correct
11 Correct 1990 ms 216716 KB Output is correct
12 Correct 2365 ms 221908 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1182 ms 227792 KB Output is correct
2 Correct 1242 ms 227864 KB Output is correct
3 Correct 889 ms 199188 KB Output is correct
4 Correct 800 ms 199180 KB Output is correct
5 Correct 875 ms 199172 KB Output is correct
6 Correct 1002 ms 205952 KB Output is correct
7 Correct 1132 ms 205880 KB Output is correct
8 Correct 1000 ms 205920 KB Output is correct
9 Correct 992 ms 203872 KB Output is correct
10 Correct 958 ms 203740 KB Output is correct
11 Correct 971 ms 203784 KB Output is correct
12 Correct 968 ms 203800 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2855 ms 363184 KB Output is correct
2 Correct 2716 ms 363276 KB Output is correct
3 Correct 2049 ms 306012 KB Output is correct
4 Correct 1934 ms 305760 KB Output is correct
5 Correct 1959 ms 305708 KB Output is correct
6 Correct 2838 ms 319344 KB Output is correct
7 Correct 2738 ms 319628 KB Output is correct
8 Correct 2605 ms 319384 KB Output is correct
9 Correct 2442 ms 315212 KB Output is correct
10 Correct 2560 ms 315292 KB Output is correct
11 Correct 2426 ms 315316 KB Output is correct
12 Correct 2469 ms 315196 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3219 ms 380348 KB Output is correct
2 Correct 3125 ms 379656 KB Output is correct
3 Correct 2895 ms 318256 KB Output is correct
4 Correct 3307 ms 323724 KB Output is correct
5 Correct 2798 ms 316712 KB Output is correct
6 Execution timed out 3545 ms 336936 KB Time limit exceeded
7 Halted 0 ms 0 KB -