제출 #1229660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229660		alexander707070	Prize (CEOI22_prize)	C++20	0 / 100	359 ms	133776 KiB

Main

#include<bits/stdc++.h>

#define MAXN 500007
#define MAXK 1007

using namespace std;

struct answer{
    int d1,d2,e1,e2;
}ans[MAXN];

struct path{
    int lca,a,b,da,db;
}s[MAXN];

struct equation{
    double coef[MAXK];
    int sum;
}eq[MAXK];

int n,k,q,t,p,rootv,rootw,a,b;
vector<int> v[MAXN],w[MAXN];

vector<int> tree[MAXN];

vector<int> sp,euler;
bool vis[MAXN];
int root,dep[MAXN],parent[MAXN];
int dist[MAXN],m,num[MAXN],len[MAXN],par[MAXN],val[MAXN];
bool used[MAXN];

void dfs(int x,int p){

    len[x]=len[p]+1;
    par[x]=p;

    if(sp.size()<k){
        sp.push_back(x);
        vis[x]=true;
    }

    for(int i:v[x])dfs(i,x);
}

int dfs2(int x,int p){

    vector<int> ch;
    for(int i:w[x]){
        int curr=dfs2(i,x);
        if(curr!=0)ch.push_back(curr);
    }

    if(!vis[x]){
        if(ch.empty())return 0;
        if(ch.size()==1)return ch[0];
    }

    for(int f:ch)tree[x].push_back(f);
    return x;
}

int br;


void dfs3(int x,int p){
    dep[x]=dep[p]+1;
    parent[x]=p;

    if(vis[x])euler.push_back(x);
    for(int i:tree[x])dfs3(i,x);
}

int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])x=parent[x];

    while(x!=y){
        x=parent[x];
        y=parent[y];
    }

    return x;
}

int lca2(int x,int y){
    if(len[x]<len[y])swap(x,y);
    while(len[x]>len[y])x=par[x];

    while(x!=y){
        x=par[x];
        y=par[y];
    }

    return x;
}

bool cmp(path fr,path sc){
    return dep[fr.lca] > dep[sc.lca];
}

void solve_up(int x,int d){
    if(dist[x]==0){
        dist[x]=d; return;
    }

    solve_up(parent[x],d-dist[x]);
}

void add_equation(int x,int y,int z){
    while(x!=y){
        eq[m].coef[num[x]]=1;
        x=par[x];
    }

    eq[m].sum=z; m++;
}

void subtract(int x,int y,double c){
    for(int i=0;i<k-1;i++)eq[x].coef[i]-=eq[y].coef[i]*c;
    eq[x].sum-=eq[y].sum*c;
}

void gauss(){
    for(int i=0;i<k-1;i++){
        int pos=-1;

        for(int f=i;f<m;f++){
            if(eq[f].coef[i]!=0)pos=f;
        }

        assert(pos!=-1);
        swap(eq[i],eq[pos]);

        for(int f=i+1;f<m;f++){
            subtract(f,i,eq[f].coef[i]/eq[i].coef[i]);
        }
    }

    for(int i=k-2;i>=0;i--){
        for(int f=k-2;f>i;f--){
            eq[i].sum-=val[f]*eq[i].coef[f];
        }
        val[i]=eq[i].sum/eq[i].coef[i];
    }
}

pair<int,int> dists(int x,int y){
    int xx=x,yy=y;

    int s1=0,s2=0;

    if(len[x]<len[y])swap(x,y);
    while(len[x]>len[y]){
        s1+=val[num[x]];
        x=par[x];
    }

    while(x!=y){
        s1+=val[num[x]]+val[num[y]];
        x=par[x]; y=par[y];
    }

    x=xx; y=yy;

    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y]){
        s2+=dist[x];
        x=parent[x];
    }

    while(x!=y){
        s2+=dist[x]+dist[y];
        x=parent[x]; y=parent[y];
    }

    return {s1,s2};
}

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k>>q>>t;

    for(int i=1;i<=n;i++){
        cin>>p;
        if(p!=-1)v[p].push_back(i);
        else rootv=i;
    }

    dfs(rootv,0);
    
    for(int i=1;i<=n;i++){
        cin>>p;
        if(p!=-1)w[p].push_back(i);
        else rootw=i;
    }

    root=dfs2(rootw,0);
    dfs3(root,0);

    for(int i:sp)cout<<i<<" ";
    cout<<"\n";
    for(int i=0;i<k-1;i++)cout<<"? "<<euler[i]<<" "<<euler[i+1]<<"\n";
    cout<<"!\n";

    fflush(stdout);

    for(int i=0;i<k-1;i++){
        cin>>ans[i].d1>>ans[i].d2>>ans[i].e1>>ans[i].e2;
        s[i]={1,euler[i],euler[i+1],ans[i].e1,ans[i].e2};
    }

    return 0;

    sort(s,s+k-1,cmp);

    for(int i=0;i<k-1;i++){
        solve_up(s[i].a,s[i].da);
        solve_up(s[i].b,s[i].db);
    }

    m=-1;
    for(int i:sp){num[i]=m; m++;}

    m=0;
    for(int i=0;i<k-1;i++){
        int c=lca2(euler[i],euler[i+1]);

        add_equation(euler[i],c,ans[i].d1);
        add_equation(euler[i+1],c,ans[i].d2);
    }

    gauss();

    for(int i=1;i<=t;i++){
        cin>>a>>b;

        auto curr=dists(a,b);
        cout<<curr.first<<" "<<curr.second<<"\n";
    }

    fflush(stdout);
    
    return 0;
}

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