oj.uz

Submission #1061530

# Submission time Handle Problem Language Result Execution time Memory
1061530 2024-08-16T10:34:03 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 2694 ms 237532 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=5e5+15;
const ll offset=2e5;
const ll inf=1e18;
const int base=350;
const ll mod=998244353;


vector<pii> ke[maxn],adj[maxn];
int dp[maxn],par[maxn][21],in[maxn],out[maxn],Time,dep[maxn];
void dfs(int u,int pre)
{
    in[u]=++Time;
    par[u][0]=pre;
    for1(i,1,20) par[u][i]=par[par[u][i-1]][i-1];
    for(auto x: ke[u])
    {
        int v=x.fi,w=x.se;
        if (v==pre) continue;
        dep[v]=dep[u]+w;
        dfs(v,u);
    }
    out[u]=Time;
}
bool is_ancestor(int u,int v) {return in[u]<=in[v] && out[v]<=out[u];}
int lca(int u,int v)
{
    if (is_ancestor(u,v)) return u;
    if (is_ancestor(v,u)) return v;
    for2(i,20,0) if (!is_ancestor(par[u][i],v)) u=par[u][i];
    return par[u][0];
}

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
    for1(i,0,N-2)
    {
        ke[A[i]].pb({B[i],D[i]});
        ke[B[i]].pb({A[i],D[i]});
    }
    dfs(0,0);
    for1(i,0,N-1) dp[i]=inf;
}
priority_queue<pii,vector<pii>,greater<pii>> pq;
long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
    vector<int> L;
    for1(i,0,S-1) L.pb(X[i]);
    for1(i,0,T-1) L.pb(Y[i]);
    sort(all(L),[](int u,int v)
         {
             return in[u]<in[v];
         });
    for1(i,1,S+T-1)
    {
        L.pb(lca(L[i],L[i-1]));
    }
    L.pb(0);
    sort(all(L),[](int u,int v)
         {
             return in[u]<in[v];
         });
    L.resize(unique(all(L))-L.begin());
    vector<int> Q;
    for(int u: L)
    {
        while(!Q.empty() && !is_ancestor(Q.back(),u)) Q.pop_back();
        if (!Q.empty())
        {
            adj[Q.back()].pb({u,dep[u]-dep[Q.back()]});
            adj[u].pb({Q.back(),dep[u]-dep[Q.back()]});
        }
        Q.pb(u);
    }
//    return 0;
    for1(i,0,S-1)
    {
        dp[X[i]]=0;
        pq.push({0LL,X[i]});
    }
    while (!pq.empty())
    {
        int _=pq.top().fi, u=pq.top().se;
        pq.pop();
        if (_!=dp[u]) continue;
        for(pii x:adj[u])
        {
            int v=x.fi,w=x.se;
            if (dp[u]+w<dp[v])
            {
                dp[v]=dp[u]+w;
                pq.push({dp[v],v});
            }
        }
    }
    int res=inf;
    for1(i,0,T-1)
    {
        res=min(res,dp[Y[i]]);
    }
    for(int u:L)
    {
        adj[u].clear();
        dp[u]=inf;
    }
    return res;

}




/*
#define MAX_N          500000
#define MAX_Q          100000
#define MAX_SUM_ST    1000000
#define MAX_VALUE  1000000000
static int N, Q;
static int A[MAX_N], B[MAX_N], D[MAX_N];
static int S[MAX_N];
static int T[MAX_N];
static int X[MAX_SUM_ST];
static int Y[MAX_SUM_ST];

static int Qx[MAX_N];
static int Qy[MAX_N];

int32_t main() {
//  freopen("sample-in-01.txt","r",stdin);

  int i, j, k;
  int STop, TTop;

  if (2 != scanf("%d%d", &N, &Q)) {
    fprintf(stderr, "error: cannot read N and Q.\n");
    exit(1);
  }
  if (!(2 <= N && N <= MAX_N)) {
    fprintf(stderr, "error: N is out of bounds.\n");
    exit(1);
  }
  if (!(1 <= Q && Q <= MAX_Q)) {
    fprintf(stderr, "error: Q is out of bounds.\n");
    exit(1);
  }
  for (i = 0; i < N - 1; ++i) {
    if (1 != scanf("%d", &A[i])) {
      fprintf(stderr, "error: cannot read A[%d].\n", i);
      exit(1);
    }
    if (!(0 <= A[i] && A[i] <= N - 1)) {
      fprintf(stderr, "error: A[%d] is out of bounds.\n", i);
      exit(1);
    }
    if (1 != scanf("%d", &B[i])) {
      fprintf(stderr, "error: cannot read B[%d].\n", i);
      exit(1);
    }
    if (!(0 <= B[i] && B[i] <= N - 1)) {
      fprintf(stderr, "error: B[%d] is out of bounds.\n", i);
      exit(1);
    }
    if (A[i] == B[i]) {
      fprintf(stderr, "error: B[%d] is equal to A[%d].\n", i, i);
      exit(1);
    }
    if (1 != scanf("%d", &D[i])) {
      fprintf(stderr, "error: cannot read D[%d].\n", i);
      exit(1);
    }
    if (!(1 <= D[i] && D[i] <= MAX_VALUE)) {
      fprintf(stderr, "error: D[%d] is out of bounds.\n", i);
      exit(1);
    }
  }
//    return 0;
  STop = 0;
  TTop = 0;

  for (j = 0; j < Q; ++j) {
    if (2 != scanf("%d%d", &S[j], &T[j])) {
      fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
      exit(1);
    }

    if(STop + S[j] > MAX_SUM_ST) {
      fprintf(stderr, "error: S[0] + S[1] + ... + S[%d] is out of bounds.\n", j);
      exit(1);
    }

    if(TTop + T[j] > MAX_SUM_ST) {
      fprintf(stderr, "error: T[0] + T[1] + ... + T[%d] is out of bounds.\n", j);
      exit(1);
    }

    for (k = 0; k < S[j]; ++k, ++STop) {
      if (1 != scanf("%d", &X[STop])) {
        fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
        exit(1);
      }

      if (!(0 <= X[STop] && X[STop] <= N - 1)) {
        fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
        exit(1);
      }
    }

    for (k = 0; k < T[j]; ++k, ++TTop) {
      if (1 != scanf("%d", &Y[TTop])) {
        fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
        exit(1);
      }

      if (!(0 <= Y[TTop] && Y[TTop] <= N - 1)) {
        fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
        exit(1);
      }
    }
  }

  STop = 0;
  TTop = 0;
  Init(N, A, B, D);
//    return 0;
  for (j = 0; j < Q; ++j) {
    for (k = 0; k < S[j]; k++) {
        Qx[k] = X[STop++];
    }
    for (k = 0; k < T[j]; k++) {
        Qy[k] = Y[TTop++];
    }

    printf("%lld\n", Query(S[j], Qx, T[j], Qy));
  }


  return 0;
}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47704 KB Output is correct
2 Correct 850 ms 64116 KB Output is correct
3 Correct 871 ms 63844 KB Output is correct
4 Correct 805 ms 64180 KB Output is correct
5 Correct 626 ms 64084 KB Output is correct
6 Correct 681 ms 63940 KB Output is correct
7 Correct 864 ms 63908 KB Output is correct
8 Correct 812 ms 64072 KB Output is correct
9 Correct 625 ms 64332 KB Output is correct
10 Correct 651 ms 63940 KB Output is correct
11 Correct 872 ms 63728 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47708 KB Output is correct
2 Correct 1061 ms 203348 KB Output is correct
3 Correct 1307 ms 206164 KB Output is correct
4 Correct 803 ms 200620 KB Output is correct
5 Correct 886 ms 229200 KB Output is correct
6 Correct 1450 ms 207672 KB Output is correct
7 Correct 1293 ms 101032 KB Output is correct
8 Correct 666 ms 99776 KB Output is correct
9 Correct 551 ms 104524 KB Output is correct
10 Correct 1249 ms 101684 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47704 KB Output is correct
2 Correct 850 ms 64116 KB Output is correct
3 Correct 871 ms 63844 KB Output is correct
4 Correct 805 ms 64180 KB Output is correct
5 Correct 626 ms 64084 KB Output is correct
6 Correct 681 ms 63940 KB Output is correct
7 Correct 864 ms 63908 KB Output is correct
8 Correct 812 ms 64072 KB Output is correct
9 Correct 625 ms 64332 KB Output is correct
10 Correct 651 ms 63940 KB Output is correct
11 Correct 872 ms 63728 KB Output is correct
12 Correct 8 ms 47708 KB Output is correct
13 Correct 1061 ms 203348 KB Output is correct
14 Correct 1307 ms 206164 KB Output is correct
15 Correct 803 ms 200620 KB Output is correct
16 Correct 886 ms 229200 KB Output is correct
17 Correct 1450 ms 207672 KB Output is correct
18 Correct 1293 ms 101032 KB Output is correct
19 Correct 666 ms 99776 KB Output is correct
20 Correct 551 ms 104524 KB Output is correct
21 Correct 1249 ms 101684 KB Output is correct
22 Correct 2394 ms 219232 KB Output is correct
23 Correct 2017 ms 217788 KB Output is correct
24 Correct 2694 ms 223004 KB Output is correct
25 Correct 2490 ms 224276 KB Output is correct
26 Correct 2492 ms 215256 KB Output is correct
27 Correct 1696 ms 237532 KB Output is correct
28 Correct 1607 ms 213520 KB Output is correct
29 Correct 2397 ms 214124 KB Output is correct
30 Correct 2374 ms 213656 KB Output is correct
31 Correct 2464 ms 214148 KB Output is correct
32 Correct 976 ms 109316 KB Output is correct
33 Correct 969 ms 105928 KB Output is correct
34 Correct 1302 ms 100688 KB Output is correct
35 Correct 1225 ms 100516 KB Output is correct
36 Correct 1451 ms 101300 KB Output is correct
37 Correct 1451 ms 101144 KB Output is correct