답안 #943609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943609 2024-03-11T16:20:30 Z Ahmed57 Prize (CEOI22_prize) C++17
10 / 100
3118 ms 729644 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][1000015];
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[1000001][2],outt[1000001][2],timer = 0;
int P[1000001][2][20];
int PR[1000001][2][20],cost[1000001][2][20];
int DEP[1000001][2];
int dep[1000001][2];
vector<int> adj[2][1000001],vert[1000001][2];
vector<pair<int,int>> lens[1000001][2],computed[1000001][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 comp(int i,int pr,int ty){
    for(auto j:vert[i][ty]){
        comp(j,i,ty);
    }
    if(ty==0){
        sort(vert[i][ty].begin(),vert[i][ty].end(),comp1);
    }else{
        sort(vert[i][ty].begin(),vert[i][ty].end(),comp2);
    }
    vector<pair<int,int>> lol;
    for(auto j:lens[i][ty]){
        if(j.first!=i)lol.push_back({in[j.first][ty],j.second});
    }
    sort(lol.begin(),lol.end());
    int it = 0;
    for(auto j:vert[i][ty]){
        if(it==lol.size()){
            cout<<"a333"<<endl;
            exit(0);
        }
        while(lol[it].first<in[j][ty])it++;
        if(it==lol.size()){
            cout<<"a333"<<endl;
            exit(0);
        }
        int diff = lol[it].second-sum(lol[it].first,ty);
        computed[i][ty].push_back({j,diff});
        add(in[j][ty],diff,ty);
        add(outt[j][ty]+1,-diff,ty);
    }
}
void dfs2(int i,int pr,int dist,int ty){
    PR[i][ty][0] = pr;
    cost[i][ty][0] = dist;
    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:computed[i][ty]){
        if(j.first==pr)continue;
        dfs2(j.first,i,j.second,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 = n-k+1;i<=n;i++){
        cout<<i<<" ";
    }
    cout<<endl;
    for(int i = n-k+1;i<=n;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[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});
    }
    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;
    comp(st1[0],0,0);
    comp(st2[0],0,1);
    dfs2(st1[0],0,0,0);
    dfs2(st2[0],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 'void comp(long long int, long long int, long long int)':
Main.cpp:88:14: 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]
   88 |         if(it==lol.size()){
      |            ~~^~~~~~~~~~~~
Main.cpp:93:14: 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]
   93 |         if(it==lol.size()){
      |            ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:207: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]
  207 |     for(int i = 1;i<v1.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:224: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]
  224 |     for(int i = 1;i<v2.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:168:8: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  168 |     dfs(root1,0,0);
      |     ~~~^~~~~~~~~~~
Main.cpp:170:8: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  170 |     dfs(root2,0,1);
      |     ~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1876 ms 508488 KB Output is correct
2 Correct 1876 ms 535208 KB Output is correct
3 Correct 1469 ms 705712 KB Output is correct
4 Correct 1433 ms 698180 KB Output is correct
5 Correct 1581 ms 727676 KB Output is correct
6 Correct 1916 ms 728572 KB Output is correct
7 Correct 1920 ms 729644 KB Output is correct
8 Correct 1878 ms 722140 KB Output is correct
9 Correct 1441 ms 700668 KB Output is correct
10 Correct 1527 ms 720932 KB Output is correct
11 Correct 1341 ms 684384 KB Output is correct
12 Correct 1560 ms 714024 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1654 ms 460480 KB Expected integer, but "a333" found
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1109 ms 429344 KB Expected integer, but "a333" found
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2466 ms 665204 KB Expected integer, but "a333" found
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3118 ms 697068 KB Expected integer, but "a333" found
2 Halted 0 ms 0 KB -