Submission #1014660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014660		vjudge1	Prize (CEOI22_prize)	C++17	0 / 100	1224 ms	98488 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define rep2(i,l,r) for(int i=l; i<r; i++)
#define all(x) x.begin(),x.end()
#define len(x) (int)x.size();
#define fi first
#define se second
#define elif else if
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
constexpr ll LINF=1001001001001001001LL;
constexpr ll MINF=1001001001001LL;
constexpr int INF=1001001001;
struct SegTree{
    using T=pii;
    T op(T x,T y){
        return min(x,y);
    }
    T e={INF,-1};
    vector<T> tree;
    int sz;
    SegTree(int size):sz(size){
        tree.resize(sz,e);
    }
    void set(int p,T v){
        p+=sz;
        tree[p]=v;
        p>>=1;
        while(p>=1){
            tree[p]=op(tree[p*2],tree[p*2+1]);
            p>>=1;
        }
    }
    T get(int lf,int ri){
        lf+=sz;
        ri+=sz;
        T rl=e,rr=e;
        while(lf<ri){
            if(lf&1){
                rl=op(rl,tree[lf]);
                lf++;
            }
            if(ri&1){
                ri--;
                rr=op(rr,tree[ri]);
            }
            lf>>=1;
            ri>>=1;
        }
        return op(rl,rr);
    }
};
int main(){
    int N,K,Q,T;
    cin>>N>>K>>Q>>T;
    vector<int> p(N),q(N);
    int root;
    rep(i,N)cin>>p[i];
    rep(i,N)cin>>q[i];
    vector<vector<int>> gr(N);
    rep(i,N){
        if(p[i]==-1)root=i;
        else gr[p[i]-1].emplace_back(i);
    }
    vi tour;
    vi ser(N);
    vi dist(N);
    dist[root]=0;
    stack<int> vert;
    vi use;
    vert.push(root);
    while(!vert.empty()){
        int pos=vert.top();
        if(pos<0){
            tour.emplace_back(-pos-1);
            vert.pop();
            continue;
        }
        ser[pos]=tour.size();
        tour.emplace_back(pos);
        use.emplace_back(pos);
        vert.pop();
        for(int i:gr[pos]){
            dist[i]=dist[pos]+1;
            vert.push(-pos-1);
            vert.push(i);
        }
    }
    rep(i,K){
        cout<<use[i]+1;
        if(i==K-1)cout<<endl;
        else cout<<" ";
    }
    rep2(i,1,K){
        cout<<"? "<<root+1<<" "<<use[i]+1<<endl;
    }
    cout<<"!"<<endl;
    vector<int> right(N,0);
    rep2(i,1,K){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        right[use[i]]=a+b;
    }
    SegTree seg(N);
    rep(i,N){
        seg.set(i,{dist[tour[i]],tour[i]});
    }
    vi ans(T);
    rep(i,T){
        int a,b;
        cin>>a>>b;
        a--;b--;
        pii lca=seg.get(min(ser[a],ser[b]),max(ser[a],ser[b])+1);
        ans[i]=right[a]+right[b]-right[lca.se]*2;
    }
    for(int i:ans)cout<<i<<" "<<i<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:101:29: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |         cout<<"? "<<root+1<<" "<<use[i]+1<<endl;
      |                             ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24