oj.uz

Submission #780475

# Submission time Handle Problem Language Result Execution time Memory
780475 2023-07-12T09:17:30 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 2578 ms 482420 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 36 ms 55704 KB Output is correct
2 Correct 551 ms 67220 KB Output is correct
3 Correct 537 ms 67028 KB Output is correct
4 Correct 549 ms 67244 KB Output is correct
5 Correct 512 ms 67524 KB Output is correct
6 Correct 363 ms 67048 KB Output is correct
7 Correct 535 ms 67080 KB Output is correct
8 Correct 540 ms 67220 KB Output is correct
9 Correct 530 ms 67492 KB Output is correct
10 Correct 357 ms 66988 KB Output is correct
11 Correct 525 ms 67044 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55636 KB Output is correct
2 Correct 1299 ms 440284 KB Output is correct
3 Correct 1315 ms 444508 KB Output is correct
4 Correct 1106 ms 437888 KB Output is correct
5 Correct 1299 ms 479592 KB Output is correct
6 Correct 1353 ms 446032 KB Output is correct
7 Correct 848 ms 141772 KB Output is correct
8 Correct 639 ms 140984 KB Output is correct
9 Correct 851 ms 147336 KB Output is correct
10 Correct 939 ms 142896 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55704 KB Output is correct
2 Correct 551 ms 67220 KB Output is correct
3 Correct 537 ms 67028 KB Output is correct
4 Correct 549 ms 67244 KB Output is correct
5 Correct 512 ms 67524 KB Output is correct
6 Correct 363 ms 67048 KB Output is correct
7 Correct 535 ms 67080 KB Output is correct
8 Correct 540 ms 67220 KB Output is correct
9 Correct 530 ms 67492 KB Output is correct
10 Correct 357 ms 66988 KB Output is correct
11 Correct 525 ms 67044 KB Output is correct
12 Correct 26 ms 55636 KB Output is correct
13 Correct 1299 ms 440284 KB Output is correct
14 Correct 1315 ms 444508 KB Output is correct
15 Correct 1106 ms 437888 KB Output is correct
16 Correct 1299 ms 479592 KB Output is correct
17 Correct 1353 ms 446032 KB Output is correct
18 Correct 848 ms 141772 KB Output is correct
19 Correct 639 ms 140984 KB Output is correct
20 Correct 851 ms 147336 KB Output is correct
21 Correct 939 ms 142896 KB Output is correct
22 Correct 2529 ms 452200 KB Output is correct
23 Correct 2216 ms 451216 KB Output is correct
24 Correct 2578 ms 457364 KB Output is correct
25 Correct 2250 ms 460048 KB Output is correct
26 Correct 2053 ms 450248 KB Output is correct
27 Correct 2160 ms 482420 KB Output is correct
28 Correct 1577 ms 447344 KB Output is correct
29 Correct 1925 ms 448864 KB Output is correct
30 Correct 1952 ms 448212 KB Output is correct
31 Correct 1951 ms 448760 KB Output is correct
32 Correct 997 ms 150828 KB Output is correct
33 Correct 723 ms 144848 KB Output is correct
34 Correct 920 ms 140896 KB Output is correct
35 Correct 895 ms 140652 KB Output is correct
36 Correct 939 ms 141464 KB Output is correct
37 Correct 941 ms 141352 KB Output is correct