oj.uz

Submission #674744

# Submission time Handle Problem Language Result Execution time Memory
674744 2022-12-26T06:14:21 Z lam Factories (JOI14_factories) C++14
0 / 100
 3068 ms 183132 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
const int maxn = 5e5 + 10;
int n,q;
vector <ii> adj[maxn];
int s[maxn],par[maxn];
long long d[maxn];
bool dau[maxn];
vector <long long> depth[maxn];

int get_sz(int x, int p)
{
    s[x]=1;
    for (ii i:adj[x])
        if (i.ff!=p&&!dau[i.ff])
            s[x]+=get_sz(i.ff,x);
    return s[x];
}

int find_centroid(int x, int p, int sz)
{
    for (ii i:adj[x])
        if (i.ff!=p&&!dau[i.ff]&&s[i.ff]*2>sz) return find_centroid(i.ff,x,sz);
    return x;
}

void dfs(int x, int p, long long dep)
{
    depth[x].push_back(dep);
    for (ii i:adj[x])
        if (i.ff!=p&&!dau[i.ff]) dfs(i.ff,x,dep+i.ss);
}

void decompose(int x, int p)
{
    x=find_centroid(x,x,get_sz(x,x));
    dau[x]=1;
    depth[x].push_back(0);
    par[x]=p;
    d[x]=1e18;
    for (ii i:adj[x])
        if (!dau[i.ff])
        {
            dfs(i.ff,x,1LL*i.ss);
            decompose(i.ff,x);
        }
}

void color(int x)
{
    int p=x;
    for (int i=depth[x].size()-1; i>=0; i--)
    {
        long long j=depth[x][i];
        d[p]=min(d[p],j);
        p=par[p];
    }
}
long long qry(int x)
{
    int p=x;
    long long ans=1e18;
    for (int i=depth[x].size()-1; i>=0; i--)
    {
        int j=depth[x][i];
        if (d[p]!=1e18) ans=min(ans,d[p]+j);
        p=par[p];
    }
    return ans;
}
void xoa(int x)
{
    int p=x;
    for (int i=depth[x].size()-1; i>=0; i--)
    {
        int j=depth[x][i];
        d[p]=1e18;
        p=par[p];
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for (int i=1; i<=n; i++)
    {
        adj[i].clear();
        dau[i]=0;
    }
    for (int i=0; i<n-1; i++)
    {
        int u=A[i]; int v=B[i]; int w=D[i];
        u++; v++;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    decompose(1,-1);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i=0; i<S; i++) color(++X[i]);
    long long ans = 1e18;
    for (int i=0; i<T; i++) ans=min(ans,qry(++Y[i]));
    for (int i=0; i<S; i++) xoa(X[i]);
  return ans;
}

Compilation message

factories.cpp: In function 'void xoa(int)':
factories.cpp:79:13: warning: unused variable 'j' [-Wunused-variable]
   79 |         int j=depth[x][i];
      |             ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24276 KB Output is correct
2 Correct 275 ms 41932 KB Output is correct
3 Incorrect 300 ms 42212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23964 KB Output is correct
2 Correct 1994 ms 131872 KB Output is correct
3 Incorrect 3068 ms 183132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24276 KB Output is correct
2 Correct 275 ms 41932 KB Output is correct
3 Incorrect 300 ms 42212 KB Output isn't correct
4 Halted 0 ms 0 KB -