oj.uz

Submission #773913

# Submission time Handle Problem Language Result Execution time Memory
773913 2023-07-05T09:29:31 Z doowey Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 380272 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(false);
    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();
    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:154: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]
  154 |     for(int i = 0 ; i < qq.size(); i ++ ){
      |                     ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1456 ms 240744 KB Output is correct
2 Correct 1421 ms 244924 KB Output is correct
3 Correct 1518 ms 213172 KB Output is correct
4 Correct 1548 ms 212220 KB Output is correct
5 Correct 1706 ms 216132 KB Output is correct
6 Correct 1889 ms 221216 KB Output is correct
7 Correct 1814 ms 221144 KB Output is correct
8 Correct 1821 ms 220452 KB Output is correct
9 Correct 1503 ms 213040 KB Output is correct
10 Correct 1625 ms 215456 KB Output is correct
11 Correct 1447 ms 210616 KB Output is correct
12 Correct 1540 ms 214664 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1598 ms 245044 KB Output is correct
2 Correct 1408 ms 239008 KB Output is correct
3 Correct 1728 ms 213188 KB Output is correct
4 Correct 1845 ms 216544 KB Output is correct
5 Correct 1883 ms 214136 KB Output is correct
6 Correct 2107 ms 217792 KB Output is correct
7 Correct 2341 ms 222332 KB Output is correct
8 Correct 2157 ms 222880 KB Output is correct
9 Correct 2012 ms 221052 KB Output is correct
10 Correct 2146 ms 222160 KB Output is correct
11 Correct 2298 ms 216664 KB Output is correct
12 Correct 2487 ms 221848 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 999 ms 227868 KB Output is correct
2 Correct 1037 ms 227916 KB Output is correct
3 Correct 721 ms 199196 KB Output is correct
4 Correct 733 ms 199132 KB Output is correct
5 Correct 724 ms 199216 KB Output is correct
6 Correct 999 ms 205924 KB Output is correct
7 Correct 994 ms 205908 KB Output is correct
8 Correct 900 ms 205940 KB Output is correct
9 Correct 798 ms 203916 KB Output is correct
10 Correct 860 ms 203800 KB Output is correct
11 Correct 929 ms 203928 KB Output is correct
12 Correct 820 ms 203776 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2197 ms 363300 KB Output is correct
2 Correct 2296 ms 363224 KB Output is correct
3 Correct 1616 ms 306032 KB Output is correct
4 Correct 1581 ms 305856 KB Output is correct
5 Correct 1601 ms 305768 KB Output is correct
6 Correct 2401 ms 319376 KB Output is correct
7 Correct 2396 ms 319504 KB Output is correct
8 Correct 2673 ms 319336 KB Output is correct
9 Correct 2476 ms 315268 KB Output is correct
10 Correct 2412 ms 315364 KB Output is correct
11 Correct 2257 ms 315168 KB Output is correct
12 Correct 2000 ms 315192 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3226 ms 380272 KB Output is correct
2 Correct 2767 ms 379404 KB Output is correct
3 Correct 2528 ms 318152 KB Output is correct
4 Correct 2884 ms 323776 KB Output is correct
5 Correct 2695 ms 316768 KB Output is correct
6 Execution timed out 3553 ms 337136 KB Time limit exceeded
7 Halted 0 ms 0 KB -