oj.uz

Submission #773895

# Submission time Handle Problem Language Result Execution time Memory
773895 2023-07-05T09:22:05 Z doowey Prize (CEOI22_prize) C++14
100 / 100
 3497 ms 380252 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::sync_with_stdio(false);
    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();
    fflush(stdout);
    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 1318 ms 240772 KB Output is correct
2 Correct 1364 ms 244876 KB Output is correct
3 Correct 1520 ms 213168 KB Output is correct
4 Correct 1443 ms 212080 KB Output is correct
5 Correct 1600 ms 216132 KB Output is correct
6 Correct 1799 ms 221208 KB Output is correct
7 Correct 1847 ms 221188 KB Output is correct
8 Correct 1688 ms 220172 KB Output is correct
9 Correct 1589 ms 212952 KB Output is correct
10 Correct 1569 ms 215424 KB Output is correct
11 Correct 1440 ms 210600 KB Output is correct
12 Correct 1633 ms 214640 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1785 ms 245044 KB Output is correct
2 Correct 1582 ms 238940 KB Output is correct
3 Correct 1770 ms 213300 KB Output is correct
4 Correct 1858 ms 216540 KB Output is correct
5 Correct 1729 ms 214236 KB Output is correct
6 Correct 1944 ms 217924 KB Output is correct
7 Correct 2133 ms 222432 KB Output is correct
8 Correct 2164 ms 222908 KB Output is correct
9 Correct 2016 ms 221004 KB Output is correct
10 Correct 1992 ms 222176 KB Output is correct
11 Correct 1781 ms 216764 KB Output is correct
12 Correct 2080 ms 221964 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 227864 KB Output is correct
2 Correct 849 ms 227880 KB Output is correct
3 Correct 613 ms 199100 KB Output is correct
4 Correct 644 ms 199264 KB Output is correct
5 Correct 671 ms 199216 KB Output is correct
6 Correct 846 ms 205924 KB Output is correct
7 Correct 830 ms 205992 KB Output is correct
8 Correct 802 ms 205936 KB Output is correct
9 Correct 736 ms 203880 KB Output is correct
10 Correct 748 ms 203740 KB Output is correct
11 Correct 745 ms 203812 KB Output is correct
12 Correct 697 ms 203968 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2127 ms 363208 KB Output is correct
2 Correct 2215 ms 363276 KB Output is correct
3 Correct 1564 ms 306124 KB Output is correct
4 Correct 1597 ms 305880 KB Output is correct
5 Correct 1518 ms 305676 KB Output is correct
6 Correct 2201 ms 319396 KB Output is correct
7 Correct 2672 ms 319544 KB Output is correct
8 Correct 2558 ms 319416 KB Output is correct
9 Correct 2008 ms 315184 KB Output is correct
10 Correct 2068 ms 315388 KB Output is correct
11 Correct 1925 ms 315284 KB Output is correct
12 Correct 2152 ms 315256 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2706 ms 380252 KB Output is correct
2 Correct 2772 ms 379508 KB Output is correct
3 Correct 2514 ms 318156 KB Output is correct
4 Correct 2764 ms 323700 KB Output is correct
5 Correct 2439 ms 316772 KB Output is correct
6 Correct 3497 ms 337040 KB Output is correct
7 Correct 3083 ms 330804 KB Output is correct
8 Correct 3300 ms 334616 KB Output is correct
9 Correct 2947 ms 329644 KB Output is correct
10 Correct 2969 ms 328156 KB Output is correct
11 Correct 2894 ms 328092 KB Output is correct
12 Correct 3066 ms 331200 KB Output is correct