oj.uz

Submission #1088212

# Submission time Handle Problem Language Result Execution time Memory
1088212 2024-09-14T06:52:10 Z dosts Factories (JOI14_factories) C++17
100 / 100
 2666 ms 225944 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e14;
const int N = 5e5+50;
int timer = 1;
vector<pii> edges[N];
int up[N][20],d[N],tin[N],tout[N],c[N],red[N],blue[N];

void dfs(int node,int p,int dep = 0) {
    tin[node] = timer++;
    d[node] = dep;
    up[node][0] = p;
    for (auto it : edges[node]) {
        if (it.ff == p) continue;
        dfs(it.ff,node,dep+it.ss);
    }
    tout[node] = timer-1;
}

bool anc(int a,int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
} 

int lca(int a,int b) {
    if (anc(a,b)) return a;
    if (anc(b,a)) return b;
    for (int i=19;i>=0;i--) {
        if (!anc(up[a][i],b)) a = up[a][i];
    }
    return up[a][0];
}
vi edg[N];

int solver(int node) {
    red[node] = blue[node] = inf;
    if (c[node] == 1) red[node] = d[node];
    if (c[node] == 2) blue[node] = d[node];
    int ans = inf;
    for (auto it : edg[node]) {
        ans = min(ans,solver(it));
        red[node] = min(red[node],red[it]);
        blue[node] = min(blue[node],blue[it]);
    }
    //cout << node sp red[node] sp blue[node] sp d[node]<< endl;
    ans = min(ans,red[node]+blue[node]-2*d[node]);
    return ans;
}

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
    int n = N;
    for (int i=0;i<n-1;i++) {
        edges[A[i]].push_back({B[i],D[i]});
        edges[B[i]].push_back({A[i],D[i]});
    }
    dfs(0,0);
    for (int i=1;i<20;i++) {
        for (int j=0;j<n;j++) up[j][i] = up[up[j][i-1]][i-1];
    }
}

long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
  int s = S,t = T;
  vector<int> nodes;
  for (int i=0;i<s;i++) {
      c[X[i]] = 1;
      nodes.push_back(X[i]);
  }
  for (int i=0;i<t;i++) {
      c[Y[i]] = 2;
      nodes.push_back(Y[i]);
  }
  sort(all(nodes),[&](int n1,int n2) {
      return tin[n1] < tin[n2];
  });
  for (int i=0;i<s+t;i++) {
      nodes.push_back(lca(nodes[i],nodes[(i+1)%nodes.size()]));
  }
  sort(all(nodes),[&](int n1,int n2) {
      return tin[n1] < tin[n2];
  });
  nodes.erase(unique(all(nodes)),nodes.end()); 
  stack<int> st;
  st.push(nodes[0]);
  for (int i=1;i<nodes.size();i++) {
      while (!anc(st.top(),nodes[i])) {
          st.pop();
      }
      edg[st.top()].push_back(nodes[i]);
      st.push(nodes[i]);
  }
  int ans = solver(nodes[0]);
  for (auto it : nodes) edg[it].clear(),c[it] = 0;
  return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int32_t, int32_t*, int32_t, int32_t*)':
factories.cpp:92:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for (int i=1;i<nodes.size();i++) {
      |                ~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24412 KB Output is correct
2 Correct 630 ms 42840 KB Output is correct
3 Correct 668 ms 42900 KB Output is correct
4 Correct 648 ms 43208 KB Output is correct
5 Correct 491 ms 43132 KB Output is correct
6 Correct 492 ms 42836 KB Output is correct
7 Correct 670 ms 42868 KB Output is correct
8 Correct 673 ms 43040 KB Output is correct
9 Correct 508 ms 43216 KB Output is correct
10 Correct 508 ms 42836 KB Output is correct
11 Correct 648 ms 42836 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24156 KB Output is correct
2 Correct 1038 ms 182952 KB Output is correct
3 Correct 1452 ms 184412 KB Output is correct
4 Correct 833 ms 180128 KB Output is correct
5 Correct 1072 ms 214988 KB Output is correct
6 Correct 1557 ms 186748 KB Output is correct
7 Correct 1137 ms 74540 KB Output is correct
8 Correct 605 ms 74352 KB Output is correct
9 Correct 584 ms 80636 KB Output is correct
10 Correct 1115 ms 76116 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24412 KB Output is correct
2 Correct 630 ms 42840 KB Output is correct
3 Correct 668 ms 42900 KB Output is correct
4 Correct 648 ms 43208 KB Output is correct
5 Correct 491 ms 43132 KB Output is correct
6 Correct 492 ms 42836 KB Output is correct
7 Correct 670 ms 42868 KB Output is correct
8 Correct 673 ms 43040 KB Output is correct
9 Correct 508 ms 43216 KB Output is correct
10 Correct 508 ms 42836 KB Output is correct
11 Correct 648 ms 42836 KB Output is correct
12 Correct 14 ms 24156 KB Output is correct
13 Correct 1038 ms 182952 KB Output is correct
14 Correct 1452 ms 184412 KB Output is correct
15 Correct 833 ms 180128 KB Output is correct
16 Correct 1072 ms 214988 KB Output is correct
17 Correct 1557 ms 186748 KB Output is correct
18 Correct 1137 ms 74540 KB Output is correct
19 Correct 605 ms 74352 KB Output is correct
20 Correct 584 ms 80636 KB Output is correct
21 Correct 1115 ms 76116 KB Output is correct
22 Correct 2207 ms 198400 KB Output is correct
23 Correct 1875 ms 200176 KB Output is correct
24 Correct 2666 ms 203056 KB Output is correct
25 Correct 2529 ms 204068 KB Output is correct
26 Correct 2354 ms 195104 KB Output is correct
27 Correct 1799 ms 225944 KB Output is correct
28 Correct 1301 ms 195468 KB Output is correct
29 Correct 2320 ms 193952 KB Output is correct
30 Correct 2275 ms 193500 KB Output is correct
31 Correct 2269 ms 193652 KB Output is correct
32 Correct 955 ms 84448 KB Output is correct
33 Correct 845 ms 77556 KB Output is correct
34 Correct 1014 ms 73268 KB Output is correct
35 Correct 977 ms 73300 KB Output is correct
36 Correct 1206 ms 73996 KB Output is correct
37 Correct 1207 ms 73808 KB Output is correct