oj.uz

Submission #968550

# Submission time Handle Problem Language Result Execution time Memory
968550 2024-04-23T15:20:01 Z anton Prize (CEOI22_prize) C++17
0 / 100
 1523 ms 547280 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>


const int P = 22;
struct Tree{
    int len;
    vector<pii> anc;
    vector<int> dpth;
    vector<vector<pii>> ch;
    vector<vector<pii>> bl;

    pii& get_ch(int u, int v){
        int cur=  0;
        for(int step = (1<<22); step>=1; step/=2){
            if(cur+step<ch[u].size()){
                if(ch[u][cur+step].first<=v){
                    cur+=step;
                }
            }
        }
        return ch[u][cur];
    }

    void dfs(int u, int d){
        dpth[u]= d;
        for(auto v: ch[u]){
            dfs(v.first, d+1);
        }
    }
    int root =0;
    Tree(int sz){
        len = sz;
        anc.resize(sz);
        ch.resize(sz);
        dpth.resize(sz);
        for(int i = 0; i<sz; i++){
            cin>>anc[i].first;
            
            if(anc[i].first ==-1){
                root = i;
            }
            else{
                anc[i].first--;
                ch[anc[i].first].push_back({i, 0});

            }
        }
        for(int i = 0; i<sz; i++){
            sort(ch[i].begin(), ch[i].end());
        }
        dfs(root, 0);
    }

    void select(int u, int need, vector<int>& s, vector<pii>& queries){
        if(need ==s.size()){
            return;
        }
        if(u!=root){
            queries.push_back({anc[u].first, u});
        }
        s.push_back(u);
        for(auto v: ch[u]){
            select(v.first, need, s, queries);
        }
    }

    void build_bl(){
        bl.resize(22, vector<pii>(len));
        for(int i = 0; i<len; i++){
            if(i!=root){
                bl[0][i]  =anc[i];
            }
            else{
                bl[0][i] = {root, 0};
            }
        }
        for(int p = 1; p<P; p++){
            for(int i = 0; i<len; i++){
                bl[p][i] = {bl[p-1][bl[p-1][i].first].first, bl[p-1][i].second + bl[p-1][bl[p-1][i].first].second};
            }
        }
    }

    int sum_on_path(int u, int v){
        if(dpth[u]<dpth[v]){
            swap(u, v);
        }
    
        //cout<<"p "<<u<<" "<<v<<endl;
        int res= 0;
        for(int step =P-1; step>=0; step--){
            if(dpth[bl[step][u].first] >= dpth[v]){
                res += bl[step][u].second;
                u = bl[step][u].first;
            }
        }
        for(int step =P-1; step>=0; step--){
            if(bl[step][u].first != bl[step][v].first){
                res += bl[step][u].second + bl[step][v].second;
                u = bl[step][u].first;
                v = bl[step][v].first;
            }
        }
        return res;
    }
};

signed main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int n, k, q, t;
    cin>>n>>k>>q>>t;
    pair<Tree, Tree> tr = {Tree(n), Tree(n)};

    vector<int> selected;
    vector<pii> queries;
    tr.first.select(tr.first.root, k, selected, queries);

    for(auto e: selected){
        cout<<e+1<<" ";
    }
    cout<<endl;
    for(auto e: queries){
        cout<<"? "<<e.first+1<<" "<<e.second+1<<endl;
    }

    cout<<"!"<<endl;
    cout.flush();

    for(auto e: queries){
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        tr.first.get_ch(e.first, e.second).second = b;
        tr.first.anc[e.second].second=  b;
        //cout<<"anc "<<e.second<<endl;
    }

    tr.first.build_bl();

    for(int i = 0; i<t; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        int r= tr.first.sum_on_path(a, b);
        cout<<r<<" "<<r<<endl;
    }
    cout.flush();
}

Compilation message

Main.cpp: In member function 'std::pair<long long int, long long int>& Tree::get_ch(long long int, long long int)':
Main.cpp:19:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             if(cur+step<ch[u].size()){
      |                ~~~~~~~~^~~~~~~~~~~~~
Main.cpp: In member function 'void Tree::select(long long int, long long int, std::vector<long long int>&, std::vector<std::pair<long long int, long long int> >&)':
Main.cpp:59:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         if(need ==s.size()){
      |            ~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 666 ms 274420 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 699 ms 275084 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 570 ms 272712 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1523 ms 545084 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1516 ms 547280 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -