oj.uz

Submission #878530

# Submission time Handle Problem Language Result Execution time Memory
878530 2023-11-24T16:29:51 Z cpptowin Factories (JOI14_factories) C++17
15 / 100
 8000 ms 143684 KB 
#include"factories.h"
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define pb emplace_back
#define inf 1000000000
#define pii pair<int,int >
#define vii vector<pii>
#define vi vector<int >
using namespace std;
vii ke[maxn];
int par[maxn][20],sz[maxn];
long long d[maxn];
int ind[maxn],head[maxn],cnt = 1;
vector<array<long long,3>> adj[maxn];
void dfs(int u,int parent)
{
    sz[u] = 1;
    for(auto [v,w] : ke[u])
    {
        if(v == parent) continue;
        par[v][0] = u;
        d[v] = d[u] + w;
        dfs(v,u);
        sz[u] += sz[v];
    }
}
void hld(int u,int parent)
{
    if(head[cnt] == 0) head[cnt] = u;
    ind[u] = cnt;
    int  sc = -1,maxx = -1;
    for(auto [v,w] : ke[u]) if(v != parent)
        {
            if(maxx < sz[v])
            {
                maxx = sz[v];
                sc = v;
            }
        }
    if(sc != -1) hld(sc,u);
    for(auto [v,w] : ke[u]) if(v != parent and v != sc)
        {
            cnt++;
            hld(v,u);
        }
}
void get(int u,int t)
{
    long long val = d[u];
    int uchain,vchain = ind[1];
    while(1)
    {
        uchain = ind[u];
        adj[uchain].push_back({u,val,t});
        if(uchain == vchain) return;
        u = ind[u];
        u = par[head[u]][0];
    }
}
void Init(int N,int A[],int B[],int D[])
{
    fo(i,0,N - 2)
    {
        ke[A[i] + 1].pb(B[i] + 1,D[i]);
        ke[B[i] + 1].pb(A[i] + 1,D[i]);
    }
    dfs(1,1);
    hld(1,1);
}
long long Query(int S, int X[], int T, int Y[])
{
    long long ans = 2e18;
    fo(i,0,S - 1) get(X[i] + 1,0);
    fo(i,0,T - 1) get(Y[i] + 1,1);
    fo(i,1,cnt)
    {
        long long minn[2];
        minn[0] = minn[1] = 2e18;
        sort(adj[i].begin(),adj[i].end(),[](array<long long,3> a,array<long long,3> b)
        {
            return d[a[0]] > d[b[0]];
        });
        for(auto [v,dist,t] : adj[i])
        {
            ans = min(ans,minn[1 - t] - 2 * d[v] + dist);
            minn[t] = min(minn[t],dist);
        }
        adj[i].clear();
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 72284 KB Output is correct
2 Correct 408 ms 79064 KB Output is correct
3 Correct 380 ms 79076 KB Output is correct
4 Correct 400 ms 88648 KB Output is correct
5 Correct 327 ms 88916 KB Output is correct
6 Correct 290 ms 88388 KB Output is correct
7 Correct 383 ms 88656 KB Output is correct
8 Correct 388 ms 88660 KB Output is correct
9 Correct 298 ms 88776 KB Output is correct
10 Correct 291 ms 88404 KB Output is correct
11 Correct 372 ms 88684 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 72460 KB Output is correct
2 Execution timed out 8070 ms 143684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 72284 KB Output is correct
2 Correct 408 ms 79064 KB Output is correct
3 Correct 380 ms 79076 KB Output is correct
4 Correct 400 ms 88648 KB Output is correct
5 Correct 327 ms 88916 KB Output is correct
6 Correct 290 ms 88388 KB Output is correct
7 Correct 383 ms 88656 KB Output is correct
8 Correct 388 ms 88660 KB Output is correct
9 Correct 298 ms 88776 KB Output is correct
10 Correct 291 ms 88404 KB Output is correct
11 Correct 372 ms 88684 KB Output is correct
12 Correct 14 ms 72460 KB Output is correct
13 Execution timed out 8070 ms 143684 KB Time limit exceeded
14 Halted 0 ms 0 KB -