Submission #984815

#	Time	Username	Problem	Language	Result	Execution time	Memory
984815		Faisal_Saqib	Cyberland (APIO23_cyberland)	C++17	0 / 100	1320 ms	2097152 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
int n,h;
const int N=1e5+10;
vector<pair<int,long long>> ma[N];
long long arr[N],down[N],dist[N][2];
long long ans=1e14+10;
void dfs(int x,int p=-1,bool pa=0)
{
    if(arr[x]==0)
    {
        pa=1;
    }
    if(x==h)
    {
        dist[x][pa]=0;
        return;
    }
    for(auto [y,w]:ma[x])
    {
        if(y!=p)
        {
            dfs(y,x);
            dist[x][1]=min(dist[x][1],dist[y][1]);
            dist[x][0]=min(dist[x][0],dist[y][0]+w);
        }
    }
    if(arr[x]==0)
        dist[x][1]=min(dist[x][1],dist[x][0]);
}
void dp(int x,int p=-1)
{
    if(arr[x]==0)
        down[x]=0;
    if(x==h)
        return;
    for(auto [y,w]:ma[x])
        if(y!=p)
        {
            dp(y,x);
            down[x]=min(down[x],w+down[y]);
        }
}
void full_solve(int x,int p=-1,long long up=0)
{
    ans=min(ans,min(down[x],up)+min(dist[x][1],dist[x][0]));
    if(x==h)
        return;
    for(auto [y,w]:ma[x])
        if(y!=p)
        {
            full_solve(y,x,min(up,down[x])+w);
        }
}
double solve(int NP, int m, int k, int HP, vector<int> x, vector<int> y, vector<int> c, vector<int> aas) {
    n=NP;
    h=HP;
    for(int i=0;i<n;i++)
    {
        ma[i].clear();
        dist[i][0]=dist[i][1]=down[i]=1e14+10;
        arr[i]=aas[i];
    }
    for(int j=0;j<m;j++)
    {
        ma[x[j]].push_back({y[j],c[j]});
        ma[y[j]].push_back({x[j],c[j]});
    }
    dfs(0);
    down[0]=0;
    dp(0);
    full_solve(0);
    double tap=ans;
    return tap;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3