oj.uz

Submission #780457

# Submission time Handle Problem Language Result Execution time Memory
780457 2023-07-12T09:09:59 Z trucmai Factories (JOI14_factories) C++17
15 / 100
 762 ms 524288 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 = 5e5 + 5,MN2 = 1e4 + 5,LOG = 27;
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 27 ms 28484 KB Output is correct
2 Correct 536 ms 40816 KB Output is correct
3 Correct 563 ms 40852 KB Output is correct
4 Correct 540 ms 41036 KB Output is correct
5 Correct 525 ms 41124 KB Output is correct
6 Correct 367 ms 40940 KB Output is correct
7 Correct 533 ms 40752 KB Output is correct
8 Correct 535 ms 41068 KB Output is correct
9 Correct 524 ms 41132 KB Output is correct
10 Correct 363 ms 40736 KB Output is correct
11 Correct 533 ms 40856 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28244 KB Output is correct
2 Runtime error 762 ms 524288 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28484 KB Output is correct
2 Correct 536 ms 40816 KB Output is correct
3 Correct 563 ms 40852 KB Output is correct
4 Correct 540 ms 41036 KB Output is correct
5 Correct 525 ms 41124 KB Output is correct
6 Correct 367 ms 40940 KB Output is correct
7 Correct 533 ms 40752 KB Output is correct
8 Correct 535 ms 41068 KB Output is correct
9 Correct 524 ms 41132 KB Output is correct
10 Correct 363 ms 40736 KB Output is correct
11 Correct 533 ms 40856 KB Output is correct
12 Correct 15 ms 28244 KB Output is correct
13 Runtime error 762 ms 524288 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -