oj.uz

Submission #773924

# Submission time Handle Problem Language Result Execution time Memory
773924 2023-07-05T09:33:51 Z doowey Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 380372 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(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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";
    cout.flush();
    for(auto x : qq){
        cout << "? " << x.fi << " " << x.se << "\n";
    }
    cout << "!\n";
    cout.flush();
    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";
    }
    cout.flush();
    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:153: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]
  153 |     for(int i = 0 ; i < qq.size(); i ++ ){
      |                     ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1430 ms 240748 KB Output is correct
2 Correct 1704 ms 244908 KB Output is correct
3 Correct 1548 ms 213252 KB Output is correct
4 Correct 1625 ms 212152 KB Output is correct
5 Correct 1688 ms 216128 KB Output is correct
6 Correct 1953 ms 221312 KB Output is correct
7 Correct 1835 ms 221140 KB Output is correct
8 Correct 1773 ms 220284 KB Output is correct
9 Correct 1515 ms 212952 KB Output is correct
10 Correct 1617 ms 215416 KB Output is correct
11 Correct 1450 ms 210616 KB Output is correct
12 Correct 1627 ms 214648 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1597 ms 245012 KB Output is correct
2 Correct 1456 ms 238900 KB Output is correct
3 Correct 1713 ms 213276 KB Output is correct
4 Correct 1788 ms 216552 KB Output is correct
5 Correct 1846 ms 214124 KB Output is correct
6 Correct 1939 ms 217772 KB Output is correct
7 Correct 2185 ms 222568 KB Output is correct
8 Correct 2210 ms 223004 KB Output is correct
9 Correct 1968 ms 220976 KB Output is correct
10 Correct 2069 ms 222160 KB Output is correct
11 Correct 1827 ms 216632 KB Output is correct
12 Correct 2069 ms 221848 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 889 ms 227840 KB Output is correct
2 Correct 861 ms 227888 KB Output is correct
3 Correct 649 ms 199200 KB Output is correct
4 Correct 654 ms 199348 KB Output is correct
5 Correct 621 ms 199216 KB Output is correct
6 Correct 834 ms 205924 KB Output is correct
7 Correct 823 ms 205952 KB Output is correct
8 Correct 877 ms 205940 KB Output is correct
9 Correct 782 ms 203836 KB Output is correct
10 Correct 739 ms 203812 KB Output is correct
11 Correct 749 ms 203824 KB Output is correct
12 Correct 729 ms 203840 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2214 ms 363224 KB Output is correct
2 Correct 2318 ms 363288 KB Output is correct
3 Correct 1500 ms 305936 KB Output is correct
4 Correct 1554 ms 305904 KB Output is correct
5 Correct 1571 ms 305764 KB Output is correct
6 Correct 2269 ms 319488 KB Output is correct
7 Correct 2277 ms 319596 KB Output is correct
8 Correct 2419 ms 319392 KB Output is correct
9 Correct 1960 ms 315412 KB Output is correct
10 Correct 2097 ms 315292 KB Output is correct
11 Correct 2065 ms 315216 KB Output is correct
12 Correct 2204 ms 315200 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2751 ms 380372 KB Output is correct
2 Correct 2693 ms 379416 KB Output is correct
3 Correct 2498 ms 318160 KB Output is correct
4 Correct 2807 ms 323644 KB Output is correct
5 Correct 2414 ms 316848 KB Output is correct
6 Execution timed out 3591 ms 337040 KB Time limit exceeded
7 Halted 0 ms 0 KB -