oj.uz

Submission #773901

# Submission time Handle Problem Language Result Execution time Memory
773901 2023-07-05T09:26:13 Z doowey Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 380256 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);
    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 1305 ms 240784 KB Output is correct
2 Correct 1563 ms 244868 KB Output is correct
3 Correct 1647 ms 213176 KB Output is correct
4 Correct 1497 ms 212196 KB Output is correct
5 Correct 1691 ms 216128 KB Output is correct
6 Correct 1869 ms 221216 KB Output is correct
7 Correct 1756 ms 221200 KB Output is correct
8 Correct 1674 ms 220164 KB Output is correct
9 Correct 1525 ms 212924 KB Output is correct
10 Correct 1624 ms 215416 KB Output is correct
11 Correct 1358 ms 210584 KB Output is correct
12 Correct 1543 ms 214716 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1468 ms 245100 KB Output is correct
2 Correct 1410 ms 238864 KB Output is correct
3 Correct 1649 ms 213180 KB Output is correct
4 Correct 1860 ms 216560 KB Output is correct
5 Correct 1911 ms 214124 KB Output is correct
6 Correct 2159 ms 217752 KB Output is correct
7 Correct 2297 ms 222412 KB Output is correct
8 Correct 2613 ms 222824 KB Output is correct
9 Correct 2169 ms 221040 KB Output is correct
10 Correct 2137 ms 222168 KB Output is correct
11 Correct 2009 ms 216672 KB Output is correct
12 Correct 2201 ms 221848 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 941 ms 227796 KB Output is correct
2 Correct 919 ms 227860 KB Output is correct
3 Correct 671 ms 199188 KB Output is correct
4 Correct 731 ms 199204 KB Output is correct
5 Correct 654 ms 199240 KB Output is correct
6 Correct 859 ms 205920 KB Output is correct
7 Correct 894 ms 205988 KB Output is correct
8 Correct 909 ms 206024 KB Output is correct
9 Correct 771 ms 203832 KB Output is correct
10 Correct 779 ms 203796 KB Output is correct
11 Correct 775 ms 203852 KB Output is correct
12 Correct 765 ms 203780 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2376 ms 363172 KB Output is correct
2 Correct 2162 ms 363316 KB Output is correct
3 Correct 1628 ms 306152 KB Output is correct
4 Correct 1589 ms 305888 KB Output is correct
5 Correct 1691 ms 305748 KB Output is correct
6 Correct 2144 ms 319400 KB Output is correct
7 Correct 2354 ms 319556 KB Output is correct
8 Correct 2392 ms 319436 KB Output is correct
9 Correct 2219 ms 315232 KB Output is correct
10 Correct 1996 ms 315340 KB Output is correct
11 Correct 2173 ms 315156 KB Output is correct
12 Correct 1932 ms 315208 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2797 ms 380256 KB Output is correct
2 Correct 2681 ms 379432 KB Output is correct
3 Correct 2519 ms 318160 KB Output is correct
4 Correct 2858 ms 323648 KB Output is correct
5 Correct 2442 ms 316824 KB Output is correct
6 Execution timed out 3529 ms 337264 KB Time limit exceeded
7 Halted 0 ms 0 KB -