oj.uz

Submission #878602

# Submission time Handle Problem Language Result Execution time Memory
878602 2023-11-24T21:55:48 Z cpptowin Factories (JOI14_factories) C++17
15 / 100
 8000 ms 160244 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 fi first
#define se second
#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;
long long minn[maxn][20];
vector<array<long long,4>> adj;
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.push_back({(long long)uchain,(long long)u,val,(long long)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);
    sort(adj.begin(),adj.end(),[](array<long long,4> a,array<long long,4> b)
    {
        return d[a[1]] > d[b[1]];
    });
    fo(i,1,cnt) fo(j,0,1) minn[i][j] = 2e18;
    for(auto [p,v,dist,t] : adj)
    {
        ans = min(ans,minn[p][1 - t] - 2 * d[v] + dist);
        minn[p][t] = min(minn[p][t],dist);
    }
    adj.clear();
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49756 KB Output is correct
2 Correct 661 ms 56940 KB Output is correct
3 Correct 488 ms 65732 KB Output is correct
4 Correct 521 ms 66516 KB Output is correct
5 Correct 302 ms 63968 KB Output is correct
6 Correct 390 ms 66016 KB Output is correct
7 Correct 496 ms 65844 KB Output is correct
8 Correct 481 ms 66144 KB Output is correct
9 Correct 301 ms 64012 KB Output is correct
10 Correct 384 ms 66052 KB Output is correct
11 Correct 465 ms 65872 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 49752 KB Output is correct
2 Execution timed out 8064 ms 160244 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49756 KB Output is correct
2 Correct 661 ms 56940 KB Output is correct
3 Correct 488 ms 65732 KB Output is correct
4 Correct 521 ms 66516 KB Output is correct
5 Correct 302 ms 63968 KB Output is correct
6 Correct 390 ms 66016 KB Output is correct
7 Correct 496 ms 65844 KB Output is correct
8 Correct 481 ms 66144 KB Output is correct
9 Correct 301 ms 64012 KB Output is correct
10 Correct 384 ms 66052 KB Output is correct
11 Correct 465 ms 65872 KB Output is correct
12 Correct 10 ms 49752 KB Output is correct
13 Execution timed out 8064 ms 160244 KB Time limit exceeded
14 Halted 0 ms 0 KB -