oj.uz

Submission #780459

# Submission time Handle Problem Language Result Execution time Memory
780459 2023-07-12T09:10:36 Z trucmai Factories (JOI14_factories) C++17
15 / 100
 596 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 = 1e6 + 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 37 ms 55860 KB Output is correct
2 Correct 566 ms 68336 KB Output is correct
3 Correct 568 ms 68148 KB Output is correct
4 Correct 563 ms 68336 KB Output is correct
5 Correct 527 ms 68520 KB Output is correct
6 Correct 362 ms 68172 KB Output is correct
7 Correct 543 ms 68160 KB Output is correct
8 Correct 536 ms 68320 KB Output is correct
9 Correct 529 ms 68548 KB Output is correct
10 Correct 371 ms 68128 KB Output is correct
11 Correct 550 ms 68100 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55636 KB Output is correct
2 Runtime error 596 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 55860 KB Output is correct
2 Correct 566 ms 68336 KB Output is correct
3 Correct 568 ms 68148 KB Output is correct
4 Correct 563 ms 68336 KB Output is correct
5 Correct 527 ms 68520 KB Output is correct
6 Correct 362 ms 68172 KB Output is correct
7 Correct 543 ms 68160 KB Output is correct
8 Correct 536 ms 68320 KB Output is correct
9 Correct 529 ms 68548 KB Output is correct
10 Correct 371 ms 68128 KB Output is correct
11 Correct 550 ms 68100 KB Output is correct
12 Correct 31 ms 55636 KB Output is correct
13 Runtime error 596 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -