oj.uz

Submission #780820

# Submission time Handle Problem Language Result Execution time Memory
780820 2023-07-12T13:35:28 Z trucmai Factories (JOI14_factories) C++17
100 / 100
 2249 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 40 ms 55756 KB Output is correct
2 Correct 548 ms 67100 KB Output is correct
3 Correct 543 ms 67036 KB Output is correct
4 Correct 545 ms 67212 KB Output is correct
5 Correct 526 ms 67420 KB Output is correct
6 Correct 347 ms 67048 KB Output is correct
7 Correct 531 ms 67048 KB Output is correct
8 Correct 537 ms 67304 KB Output is correct
9 Correct 517 ms 67532 KB Output is correct
10 Correct 357 ms 67104 KB Output is correct
11 Correct 531 ms 67052 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 55636 KB Output is correct
2 Correct 1283 ms 440260 KB Output is correct
3 Correct 1274 ms 444448 KB Output is correct
4 Correct 1091 ms 437780 KB Output is correct
5 Correct 1277 ms 479572 KB Output is correct
6 Correct 1374 ms 446116 KB Output is correct
7 Correct 809 ms 141896 KB Output is correct
8 Correct 626 ms 140960 KB Output is correct
9 Correct 713 ms 147404 KB Output is correct
10 Correct 785 ms 142892 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 55756 KB Output is correct
2 Correct 548 ms 67100 KB Output is correct
3 Correct 543 ms 67036 KB Output is correct
4 Correct 545 ms 67212 KB Output is correct
5 Correct 526 ms 67420 KB Output is correct
6 Correct 347 ms 67048 KB Output is correct
7 Correct 531 ms 67048 KB Output is correct
8 Correct 537 ms 67304 KB Output is correct
9 Correct 517 ms 67532 KB Output is correct
10 Correct 357 ms 67104 KB Output is correct
11 Correct 531 ms 67052 KB Output is correct
12 Correct 24 ms 55636 KB Output is correct
13 Correct 1283 ms 440260 KB Output is correct
14 Correct 1274 ms 444448 KB Output is correct
15 Correct 1091 ms 437780 KB Output is correct
16 Correct 1277 ms 479572 KB Output is correct
17 Correct 1374 ms 446116 KB Output is correct
18 Correct 809 ms 141896 KB Output is correct
19 Correct 626 ms 140960 KB Output is correct
20 Correct 713 ms 147404 KB Output is correct
21 Correct 785 ms 142892 KB Output is correct
22 Correct 2209 ms 452284 KB Output is correct
23 Correct 1948 ms 451280 KB Output is correct
24 Correct 2249 ms 457372 KB Output is correct
25 Correct 2220 ms 460176 KB Output is correct
26 Correct 1950 ms 450220 KB Output is correct
27 Correct 2151 ms 482472 KB Output is correct
28 Correct 1521 ms 447308 KB Output is correct
29 Correct 1970 ms 448836 KB Output is correct
30 Correct 1929 ms 448208 KB Output is correct
31 Correct 1911 ms 448680 KB Output is correct
32 Correct 1008 ms 150632 KB Output is correct
33 Correct 727 ms 144824 KB Output is correct
34 Correct 956 ms 140844 KB Output is correct
35 Correct 885 ms 140660 KB Output is correct
36 Correct 942 ms 141504 KB Output is correct
37 Correct 899 ms 141412 KB Output is correct