oj.uz

Submission #1048026

# Submission time Handle Problem Language Result Execution time Memory
1048026 2024-08-07T20:24:53 Z beaconmc Factories (JOI14_factories) C++14
33 / 100
 8000 ms 337552 KB 
#include "factories.h"

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
const ll INF = 1000000000000000;
vector<vector<ll>> edges[500005];
ll ancc[500005][30];
ll par[500005];
ll depth[500005];
ll realdepth[500005];
ll tin[500005];
ll timer = 0;
ll anc(ll a, ll x){
  if (a==0) return 0;
  if (x==0) return par[a];
  if (ancc[a][x] != -1) return ancc[a][x];
  return ancc[a][x] = anc(anc(a, x-1), x-1);
}

ll lca(ll a, ll b){
  if (depth[a] < depth[b]) swap(a,b);

  FORNEG(i,29,-1) if (depth[anc(a,i)] >= depth[b]) a = anc(a,i);
  if (a==b) return a;
  FORNEG(i,29,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
  return par[a];
}

void dfs(ll a, ll p, ll d, ll dd){
  tin[a] = timer++;
  par[a] = p;
  depth[a] = d;
  realdepth[a] = dd;

  for (auto&i : edges[a]){
    if (i[0] != p) dfs(i[0], a, d+1, dd+i[1]);
  }
}
void Init(int N, int A[], int B[], int D[]) {
  FOR(i,0,500005) edges[i].clear(), par[i] = -1, depth[i] = 0, realdepth[i] = -1;
  FOR(i,0,500005) FOR(j,0,30) ancc[i][j] = -1;

  FOR(i,0,N){
    edges[A[i]].push_back({B[i], D[i]});
    edges[B[i]].push_back({A[i], D[i]});
  }
  dfs(0, -1, 0,0);

}
ll mina[500005];
ll minb[500005];
vector<vector<ll>> vtree[500005];
void dp(ll a){
  for (auto&i : vtree[a]){
    dp(i[0]);
    mina[a] = min(mina[a], mina[i[0]] + i[1]);
    minb[a] = min(minb[a], minb[i[0]] + i[1]);
  }

}

long long Query(int S, int X[], int T, int Y[]) {
  vector<vector<ll>> stuff;
  FOR(i,0,S) stuff.push_back({tin[X[i]],X[i]});
  FOR(i,0,T) stuff.push_back({tin[Y[i]], Y[i]});

  sort(stuff.begin(), stuff.end());
  set<vector<ll>> stuff2;


  FOR(i,1,stuff.size()){
    stuff2.insert({tin[lca(stuff[i][1], stuff[i-1][1])], lca(stuff[i][1], stuff[i-1][1])});
  }
  if (stuff.size()){
    ll temp = lca(stuff[0][1], stuff[stuff.size()-1][1]);
    stuff2.insert({tin[temp], temp});
  }

  for (auto&i : stuff) stuff2.insert(i);

  vector<ll> stack;
  for (auto&i : stuff2) mina[i[1]] = INF, minb[i[1]] = INF, vtree[i[1]].clear();

  FOR(i,0,S) mina[X[i]] = 0;
  FOR(i,0,T) minb[Y[i]] = 0;
  for (auto&i : stuff2){
    while (stack.size() && lca(stack[stack.size()-1], i[1])!= stack[stack.size()-1])stack.pop_back();
    if (stack.size()) vtree[stack[stack.size()-1]].push_back({i[1], realdepth[i[1]] - realdepth[stack[stack.size()-1]]});
    stack.push_back(i[1]);
  }

  dp((*stuff2.begin())[1]);


  ll ans = INF;
  for (auto&i : stuff2) ans = min(ans, mina[i[1]] + minb[i[1]]);
  



  return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:6:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   76 |   FOR(i,1,stuff.size()){
      |       ~~~~~~~~~~~~~~~~           
factories.cpp:76:3: note: in expansion of macro 'FOR'
   76 |   FOR(i,1,stuff.size()){
      |   ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 169040 KB Output is correct
2 Correct 2270 ms 184004 KB Output is correct
3 Correct 2737 ms 183516 KB Output is correct
4 Correct 2360 ms 184336 KB Output is correct
5 Correct 1676 ms 184248 KB Output is correct
6 Correct 1726 ms 183768 KB Output is correct
7 Correct 2716 ms 183376 KB Output is correct
8 Correct 2414 ms 184344 KB Output is correct
9 Correct 1682 ms 184252 KB Output is correct
10 Correct 1744 ms 183860 KB Output is correct
11 Correct 2704 ms 183632 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 168784 KB Output is correct
2 Correct 2441 ms 268788 KB Output is correct
3 Correct 3859 ms 276308 KB Output is correct
4 Correct 1432 ms 262828 KB Output is correct
5 Correct 3674 ms 318796 KB Output is correct
6 Correct 3937 ms 277044 KB Output is correct
7 Correct 3785 ms 204112 KB Output is correct
8 Correct 1735 ms 201424 KB Output is correct
9 Correct 2564 ms 211732 KB Output is correct
10 Correct 3800 ms 204652 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 169040 KB Output is correct
2 Correct 2270 ms 184004 KB Output is correct
3 Correct 2737 ms 183516 KB Output is correct
4 Correct 2360 ms 184336 KB Output is correct
5 Correct 1676 ms 184248 KB Output is correct
6 Correct 1726 ms 183768 KB Output is correct
7 Correct 2716 ms 183376 KB Output is correct
8 Correct 2414 ms 184344 KB Output is correct
9 Correct 1682 ms 184252 KB Output is correct
10 Correct 1744 ms 183860 KB Output is correct
11 Correct 2704 ms 183632 KB Output is correct
12 Correct 40 ms 168784 KB Output is correct
13 Correct 2441 ms 268788 KB Output is correct
14 Correct 3859 ms 276308 KB Output is correct
15 Correct 1432 ms 262828 KB Output is correct
16 Correct 3674 ms 318796 KB Output is correct
17 Correct 3937 ms 277044 KB Output is correct
18 Correct 3785 ms 204112 KB Output is correct
19 Correct 1735 ms 201424 KB Output is correct
20 Correct 2564 ms 211732 KB Output is correct
21 Correct 3800 ms 204652 KB Output is correct
22 Correct 5666 ms 304480 KB Output is correct
23 Correct 5251 ms 305308 KB Output is correct
24 Correct 7039 ms 316248 KB Output is correct
25 Correct 6849 ms 316824 KB Output is correct
26 Correct 7531 ms 286232 KB Output is correct
27 Correct 5643 ms 337552 KB Output is correct
28 Correct 3075 ms 290052 KB Output is correct
29 Execution timed out 8015 ms 283648 KB Time limit exceeded
30 Halted 0 ms 0 KB -