oj.uz

답안 #1014652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1014652 2024-07-05T08:55:40 Z vjudge1 Prize (CEOI22_prize) C++17
0 / 100
 908 ms 98420 KB 
#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<<" ";
    }
    cout<<endl;
    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]});
    }
    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);
        cout<<right[a]+right[b]-right[lca.se]*2<<" "<<right[a]+right[b]-right[lca.se]*2<<endl;
    }
}

Compilation message

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 512 ms 49480 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 486 ms 49400 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 413 ms 49304 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 875 ms 98420 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 908 ms 98340 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -