답안 #943847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943847 2024-03-12T02:28:15 Z Ahmed57 Prize (CEOI22_prize) C++17
10 / 100
3500 ms 813688 KB
#include "bits/stdc++.h"
 
using namespace std;
#define int long long
#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#endif
int n;
int bit[2][1300015];
void add(int e,int v,int ty){
    while(e<=n){
        bit[ty][e]+=v;
        e+=e&-e;
    }
}
int sum(int e,int ty){
    int su = 0;
    while(e>=1){
        su+=bit[ty][e];
        e-=e&-e;
    }
    return su;
}
int in[1300001][2],outt[1300001][2],timer = 0;
int P[1300001][2][20];
int PR[1300001][2][20],cost[1300001][2][20];
int DEP[1300001][2];
int dep[1300001][2];
int root[1300001][2],vis[1300001][2];
vector<int> adj[2][1300001],vert[1300001][2];
vector<pair<int,int>> lens[1300001][2],computed[1300001][2];
void dfs(int i,int pr,int ty){
    in[i][ty] = ++timer;
    P[i][ty][0] = pr;
    dep[i][ty] = dep[pr][ty]+1;
    for(int j = 1;j<20;j++){
        P[i][ty][j] = P[P[i][ty][j-1]][ty][j-1];
    }
    for(auto j:adj[ty][i]){
        if(j==pr)continue;
        dfs(j,i,ty);
    }
    outt[i][ty] = timer;
}
bool comp1(int a,int b){
    return in[a][0]<in[b][0];
}
bool comp2(int a,int b){
    return in[a][1]<in[b][1];
}
int lca(int a,int b,int ty){
    if(dep[a][ty]<dep[b][ty])swap(a,b);
    for(int i = 19;i>=0;i--){
        if(dep[a][ty]-(1<<i)>=dep[b][ty]){
            a = P[a][ty][i];
        }
    }
    if(a==b)return a;
    for(int i = 19;i>=0;i--){
        if(P[a][ty][i]!=P[b][ty][i]){
            a = P[a][ty][i];
            b = P[b][ty][i];
        }
    }
    return P[a][ty][0];
}
bool upper(int a,int b,int ty){
    return in[a][ty]<=in[b][ty]&&outt[a][ty]>=outt[b][ty];
}
void dfs3(int i,int pr,int cost,int ty){
    root[i][ty] = cost;
    vis[i][ty] = 1;
    for(auto j:lens[i][ty]){
        if(!vis[j.first][ty]){
            dfs3(j.first,i,cost+j.second,ty);
        }
    }
}
void dfs2(int i,int pr,int ty){
    PR[i][ty][0] = pr;
    cost[i][ty][0] = root[i][ty]-root[pr][ty];
    DEP[i][ty] = DEP[pr][ty]+1;
    for(int j = 1;j<20;j++){
        PR[i][ty][j] = PR[PR[i][ty][j-1]][ty][j-1];
        cost[i][ty][j] = cost[i][ty][j-1]+cost[PR[i][ty][j-1]][ty][j-1];
    }
    for(auto j:vert[i][ty]){
        if(j==pr)continue;
        dfs2(j,i,ty);
    }
}
int lca2(int a,int b,int ty){
    if(DEP[a][ty]<DEP[b][ty])swap(a,b);
    int summ = 0;
    for(int i = 19;i>=0;i--){
        if(DEP[a][ty]-(1<<i)>=DEP[b][ty]){
            summ+=cost[a][ty][i];
            a = PR[a][ty][i];
        }
    }
    if(a==b)return summ;
    for(int i = 19;i>=0;i--){
        if(PR[a][ty][i]!=PR[b][ty][i]){
            summ+=cost[a][ty][i];
            summ+=cost[b][ty][i];
            a = PR[a][ty][i];
            b = PR[b][ty][i];
        }
    }
    return summ+cost[a][ty][0]+cost[b][ty][0];
}
void query(int a,int b){
    cout<<"? "<<a<<" "<<b<<endl;
    //int x,y,z,e;
    //cin>>x>>y>>z>>e;
    //return {x,y,z,e};
}
vector<pair<int,int>> queries;
vector<int> v1,st1,v2,st2;set<int> loli,loli2;
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("prize.in.1c","r",stdin);
    int k,g,t;
    cin>>n>>k>>g>>t;
    int root1 , root2;
    for(int i = 1;i<=n;i++){
        int x;cin>>x;
        if(x==-1){
            root1 = i;
        }else{
            adj[0][x].push_back(i);
            adj[0][i].push_back(x);
        }
    }
    for(int i = 1;i<=n;i++){
        int x;cin>>x;
        if(x==-1){
            root2 = i;
        }else{
            adj[1][x].push_back(i);
            adj[1][i].push_back(x);
        }
    }
    dfs(root1,0,0);
    timer = 0;
    dfs(root2,0,1);
    for(int i = 1;i<=k;i++){
        cout<<i<<" ";
    }
    cout<<endl;
    for(int i = 1;i<=k;i++){
        v1.push_back(i);
        v2.push_back(i);
    }
    sort(v1.begin(),v1.end(),comp1);
    sort(v2.begin(),v2.end(),comp1);
    for(int i = 1;i<k;i++){
        query(v1[i-1],v1[i]);
        //lens[lca(v[i],v[i-1],0)].push_back({v[i-1],lol[0]});
        //lens[lca(v[i],v[i-1],0)].push_back({v[i],lol[1]});
        v1.push_back(lca(v1[i],v1[i-1],0));
    }
    for(int i = 1;i<k;i++){
        //query(v2[i-1],v2[i]);
        //lens[lca(v[i],v[i-1],0)].push_back({v[i-1],lol[0]});
        //lens[lca(v[i],v[i-1],0)].push_back({v[i],lol[1]});
        v2.push_back(lca(v2[i],v2[i-1],1));
    }
    cout<<"!"<<endl;
    for(int i = 1;i<k;i++){
        int x,y,z,e;cin>>x>>y>>z>>e;
        lens[lca(v1[i],v1[i-1],0)][0].push_back({v1[i-1],x});
        lens[lca(v1[i],v1[i-1],0)][0].push_back({v1[i],y});
        lens[v1[i-1]][0].push_back({lca(v1[i],v1[i-1],0),-x});
        lens[v1[i]][0].push_back({lca(v1[i],v1[i-1],0),-y});
        lens[lca(v2[i],v2[i-1],1)][1].push_back({v2[i-1],z});
        lens[lca(v2[i],v2[i-1],1)][1].push_back({v2[i],e});
        lens[v2[i-1]][1].push_back({lca(v2[i],v2[i-1],1),-z});
        lens[v2[i]][1].push_back({lca(v2[i],v2[i-1],1),-e});
    }
    sort(v1.begin(),v1.end(),comp1);
    for(auto i:v1)loli.insert(i);
    v1.clear();
    for(auto i:loli)v1.push_back(i);
    sort(v1.begin(),v1.end(),comp1);
    st1.push_back(v1[0]);
    for(int i = 1;i<v1.size();i++){
        while(st1.size()>1&&!upper(st1.back(),v1[i],0)){
            vert[st1[st1.size()-2]][0].push_back(st1.back());
            st1.pop_back();
        }
        st1.push_back(v1[i]);
    }
    while(st1.size()>1){
        vert[st1[st1.size()-2]][0].push_back(st1.back());
        st1.pop_back();
    }
    sort(v2.begin(),v2.end(),comp2);
    for(auto i:v2)loli2.insert(i);
    v2.clear();
    for(auto i:loli2)v2.push_back(i);
    sort(v2.begin(),v2.end(),comp2);
    st2.push_back(v2[0]);
    for(int i = 1;i<v2.size();i++){
        while(st2.size()>1&&!upper(st2.back(),v2[i],1)){
            vert[st2[st2.size()-2]][1].push_back(st2.back());
            st2.pop_back();
        }
        st2.push_back(v2[i]);
    }
    while(st2.size()>1){
        vert[st2[st2.size()-2]][1].push_back(st2.back());
        st2.pop_back();
    }
    timer = 0;
    dfs3(st1[0],0,0,0);
    dfs3(st2[0],0,0,1);
    dfs2(st1[0],0,0);
    dfs2(st2[0],0,1);
    while(t--){
        int a,b;cin>>a>>b;
        queries.push_back({a,b});
    }
    for(auto i:queries){
        int a = i.first , b = i.second;
        cout<<lca2(a,b,0)<<" "<<lca2(a,b,1)<<endl;
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:189:20: 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]
  189 |     for(int i = 1;i<v1.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:206:20: 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]
  206 |     for(int i = 1;i<v2.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:146:8: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  146 |     dfs(root1,0,0);
      |     ~~~^~~~~~~~~~~
Main.cpp:148:8: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |     dfs(root2,0,1);
      |     ~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1774 ms 553200 KB Output is correct
2 Correct 1887 ms 581356 KB Output is correct
3 Correct 1527 ms 723644 KB Output is correct
4 Correct 1484 ms 715268 KB Output is correct
5 Correct 1641 ms 755288 KB Output is correct
6 Correct 2062 ms 758840 KB Output is correct
7 Correct 1974 ms 759516 KB Output is correct
8 Correct 1901 ms 749244 KB Output is correct
9 Correct 1483 ms 720984 KB Output is correct
10 Correct 1635 ms 748180 KB Output is correct
11 Correct 1463 ms 694596 KB Output is correct
12 Correct 1519 ms 741896 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2193 ms 578648 KB Output is correct
2 Correct 1813 ms 538316 KB Output is correct
3 Runtime error 1301 ms 716584 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1151 ms 485056 KB Output is correct
2 Correct 1239 ms 484456 KB Output is correct
3 Runtime error 800 ms 471264 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2967 ms 718120 KB Output is correct
2 Correct 2765 ms 718088 KB Output is correct
3 Runtime error 1757 ms 697564 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3583 ms 813688 KB Time limit exceeded
2 Halted 0 ms 0 KB -