oj.uz

Submission #773868

# Submission time Handle Problem Language Result Execution time Memory
773868 2023-07-05T09:12:43 Z doowey Prize (CEOI22_prize) C++14
76 / 100
 3500 ms 380244 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";
    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:152: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]
  152 |     for(int i = 0 ; i < qq.size(); i ++ ){
      |                     ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1787 ms 240732 KB Output is correct
2 Correct 1664 ms 244924 KB Output is correct
3 Correct 1721 ms 213244 KB Output is correct
4 Correct 1679 ms 212128 KB Output is correct
5 Correct 1855 ms 216224 KB Output is correct
6 Correct 2209 ms 221228 KB Output is correct
7 Correct 2199 ms 221312 KB Output is correct
8 Correct 2217 ms 220160 KB Output is correct
9 Correct 1696 ms 213100 KB Output is correct
10 Correct 1834 ms 215292 KB Output is correct
11 Correct 1785 ms 210568 KB Output is correct
12 Correct 1985 ms 214740 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1890 ms 244996 KB Output is correct
2 Correct 1898 ms 238872 KB Output is correct
3 Correct 1921 ms 213116 KB Output is correct
4 Correct 2027 ms 216540 KB Output is correct
5 Correct 1874 ms 214176 KB Output is correct
6 Correct 2104 ms 217828 KB Output is correct
7 Correct 2281 ms 222404 KB Output is correct
8 Correct 2348 ms 222896 KB Output is correct
9 Correct 2257 ms 220980 KB Output is correct
10 Correct 2311 ms 222152 KB Output is correct
11 Correct 2003 ms 216600 KB Output is correct
12 Correct 2139 ms 221860 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 227912 KB Output is correct
2 Correct 968 ms 227880 KB Output is correct
3 Correct 689 ms 199192 KB Output is correct
4 Correct 649 ms 199184 KB Output is correct
5 Correct 655 ms 199156 KB Output is correct
6 Correct 892 ms 205920 KB Output is correct
7 Correct 876 ms 205904 KB Output is correct
8 Correct 860 ms 206168 KB Output is correct
9 Correct 771 ms 203956 KB Output is correct
10 Correct 796 ms 203824 KB Output is correct
11 Correct 753 ms 203816 KB Output is correct
12 Correct 795 ms 203868 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2609 ms 363220 KB Output is correct
2 Correct 2189 ms 363204 KB Output is correct
3 Correct 1607 ms 306028 KB Output is correct
4 Correct 1623 ms 305936 KB Output is correct
5 Correct 1592 ms 305892 KB Output is correct
6 Correct 2275 ms 319488 KB Output is correct
7 Correct 2269 ms 319536 KB Output is correct
8 Correct 2470 ms 319420 KB Output is correct
9 Correct 2135 ms 315176 KB Output is correct
10 Correct 2210 ms 315248 KB Output is correct
11 Correct 2409 ms 315132 KB Output is correct
12 Correct 2364 ms 315212 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2723 ms 380244 KB Output is correct
2 Correct 2837 ms 379396 KB Output is correct
3 Correct 2581 ms 318264 KB Output is correct
4 Correct 2866 ms 323708 KB Output is correct
5 Correct 2409 ms 316772 KB Output is correct
6 Execution timed out 3570 ms 337152 KB Time limit exceeded
7 Halted 0 ms 0 KB -