oj.uz

Submission #780473

# Submission time Handle Problem Language Result Execution time Memory
780473 2023-07-12T09:16:17 Z trucmai Factories (JOI14_factories) C++17
100 / 100
 2360 ms 482472 KB 
//i_love_aisukiuwu
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
	#include "/home/trucmai/.vim/tools.h"
	#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
	#else
	#define debug(x...)
#endif

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "

const int MN1 = 1e6 + 5,MN2 = 1e4 + 5,LOG = 20;
const ll MOD = 1e9 + 7,INF = 1e18;
ll tin[MN1],tout[MN1],dis[MN1],el[MN1],h[MN1],cc[MN1]; 
ll sptin[MN1],sptout[MN1];
pi sp[MN1][LOG]; 
vector<pi>adj[MN1],vt[MN1];
ll timer = 0,sptimer = 0;

void dfs(ll u,ll pre){ 
  tin[u] = ++timer;
  sp[++sptimer][0] = {h[u],u};
  sptin[u] = sptimer;
  for(auto [v,w] : adj[u]){
    if(v == pre) continue;
    dis[v] = dis[u] + w;
    h[v] = h[u] + 1;
    dfs(v,u);
    sp[++sptimer][0] = {h[u],u};
  }
  tout[u] = timer;
}

ll lg_floor(ll u){return 63 - __builtin_clzll(u);}

void sparse(){
  for(ll i = 1;i < LOG;++i)
    for(ll j = 0;j + (1LL<<i) - 1 <= sptimer;++j)
      sp[j][i] = min(sp[j][i-1],sp[j + (1LL<<(i-1))][i-1]);
}

ll lca(ll u,ll v){
  ll tu = sptin[u],tv = sptin[v];
  if(tu > tv) swap(tu,tv);
  ll k = lg_floor(tv - tu + 1); 
  return min(sp[tu][k],sp[tv - (1LL<<k) + 1][k]).se;
}

pi dpfs(ll u,ll pre,ll &res){
  pi short_dis = {INF,INF}; 
  //cout << u << " " << pre << " " << res << endl; 
  if(cc[u] == 0) short_dis.fi = 0;
  else if(cc[u] == 1) short_dis.se = 0;
  for(auto [v,w] : vt[u]){
    if(v == pre) continue; 
    pi tmp = dpfs(v,u,res);
    //cout << tmp.fi << " " << tmp.se << endl;
    res = min(res, min(short_dis.fi + tmp.se, short_dis.se + tmp.fi) + w);
    short_dis.fi = min(short_dis.fi,tmp.fi + w);
    short_dis.se = min(short_dis.se,tmp.se + w);
  }
  debug(u,pre,short_dis,res);
  return short_dis;
}

void Init(int n, int a[],int b[],int d[]){
  mset(cc,-1);
  for(ll i = 0;i < n;++i){
    adj[a[i]].emplace_back(b[i],d[i]);
    adj[b[i]].emplace_back(a[i],d[i]);
  }
  dfs(0,0); sparse(); 
}

long long Query(int s,int x[],int t,int y[]){ 
  vector<ll>a;
  for(ll i = 0;i < s;++i){
    a.emplace_back(x[i]);
    cc[x[i]] = 0;
  }
  for(ll i = 0;i < t;++i){
    a.emplace_back(y[i]);
    cc[y[i]] = 1;
  }
  sort(all(a),[&](ll x,ll y){return tin[x] < tin[y];});
  for(ll i = 0;i + 1 < s + t;++i) a.push_back(lca(a[i],a[i+1]));  
  sort(all(a),[&](ll x,ll y){return tin[x] < tin[y];});
  a.resize(unique(all(a))-a.begin()); 
  auto is_anc=[&](ll u,ll v)->bool{
    return tin[u] <= tin[v] && tout[u] >= tin[v];
  }; 
  //create virtual tree
  stack<ll>st;
  auto add=[&](ll u,ll v,ll w)->void{
    vt[u].emplace_back(v,w); 
    vt[v].emplace_back(u,w);
  };
  for(ll i = 0;i < a.size();++i){
    while(!st.empty() && !is_anc(st.top(),a[i])) st.pop(); 
    if(!st.empty()) add(st.top(),a[i],dis[a[i]] - dis[st.top()]);
    st.push(a[i]); 
  } 
  ll res = INF;
  dpfs(a[0],0,res);
  for(ll i = 0;i < a.size();++i) vt[a[i]].clear();
  for(ll i = 0;i < s;++i) cc[x[i]] = -1;
  for(ll i = 0;i < t;++i) cc[y[i]] = -1;
  return res;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:111:18: 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]
  111 |   for(ll i = 0;i < a.size();++i){
      |                ~~^~~~~~~~~~
factories.cpp:118:18: 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]
  118 |   for(ll i = 0;i < a.size();++i) vt[a[i]].clear();
      |                ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 55716 KB Output is correct
2 Correct 574 ms 67216 KB Output is correct
3 Correct 555 ms 67036 KB Output is correct
4 Correct 545 ms 67208 KB Output is correct
5 Correct 516 ms 67420 KB Output is correct
6 Correct 356 ms 67020 KB Output is correct
7 Correct 527 ms 67052 KB Output is correct
8 Correct 546 ms 67292 KB Output is correct
9 Correct 516 ms 67424 KB Output is correct
10 Correct 365 ms 67028 KB Output is correct
11 Correct 528 ms 67188 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55640 KB Output is correct
2 Correct 1280 ms 440392 KB Output is correct
3 Correct 1258 ms 444644 KB Output is correct
4 Correct 1093 ms 437896 KB Output is correct
5 Correct 1280 ms 479508 KB Output is correct
6 Correct 1354 ms 446232 KB Output is correct
7 Correct 795 ms 141840 KB Output is correct
8 Correct 638 ms 140996 KB Output is correct
9 Correct 686 ms 147380 KB Output is correct
10 Correct 781 ms 143000 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 55716 KB Output is correct
2 Correct 574 ms 67216 KB Output is correct
3 Correct 555 ms 67036 KB Output is correct
4 Correct 545 ms 67208 KB Output is correct
5 Correct 516 ms 67420 KB Output is correct
6 Correct 356 ms 67020 KB Output is correct
7 Correct 527 ms 67052 KB Output is correct
8 Correct 546 ms 67292 KB Output is correct
9 Correct 516 ms 67424 KB Output is correct
10 Correct 365 ms 67028 KB Output is correct
11 Correct 528 ms 67188 KB Output is correct
12 Correct 29 ms 55640 KB Output is correct
13 Correct 1280 ms 440392 KB Output is correct
14 Correct 1258 ms 444644 KB Output is correct
15 Correct 1093 ms 437896 KB Output is correct
16 Correct 1280 ms 479508 KB Output is correct
17 Correct 1354 ms 446232 KB Output is correct
18 Correct 795 ms 141840 KB Output is correct
19 Correct 638 ms 140996 KB Output is correct
20 Correct 686 ms 147380 KB Output is correct
21 Correct 781 ms 143000 KB Output is correct
22 Correct 2360 ms 452164 KB Output is correct
23 Correct 2029 ms 451256 KB Output is correct
24 Correct 2341 ms 457384 KB Output is correct
25 Correct 2236 ms 460120 KB Output is correct
26 Correct 1998 ms 450268 KB Output is correct
27 Correct 2159 ms 482472 KB Output is correct
28 Correct 1587 ms 447308 KB Output is correct
29 Correct 1957 ms 448936 KB Output is correct
30 Correct 1910 ms 448176 KB Output is correct
31 Correct 1931 ms 448784 KB Output is correct
32 Correct 1022 ms 150828 KB Output is correct
33 Correct 763 ms 144808 KB Output is correct
34 Correct 926 ms 140844 KB Output is correct
35 Correct 911 ms 140568 KB Output is correct
36 Correct 945 ms 141532 KB Output is correct
37 Correct 941 ms 141488 KB Output is correct