Submission #1088212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088212		dosts	Factories (JOI14_factories)	C++17	100 / 100	2666 ms	225944 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e14;
const int N = 5e5+50;
int timer = 1;
vector<pii> edges[N];
int up[N][20],d[N],tin[N],tout[N],c[N],red[N],blue[N];

void dfs(int node,int p,int dep = 0) {
    tin[node] = timer++;
    d[node] = dep;
    up[node][0] = p;
    for (auto it : edges[node]) {
        if (it.ff == p) continue;
        dfs(it.ff,node,dep+it.ss);
    }
    tout[node] = timer-1;
}

bool anc(int a,int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
} 

int lca(int a,int b) {
    if (anc(a,b)) return a;
    if (anc(b,a)) return b;
    for (int i=19;i>=0;i--) {
        if (!anc(up[a][i],b)) a = up[a][i];
    }
    return up[a][0];
}
vi edg[N];

int solver(int node) {
    red[node] = blue[node] = inf;
    if (c[node] == 1) red[node] = d[node];
    if (c[node] == 2) blue[node] = d[node];
    int ans = inf;
    for (auto it : edg[node]) {
        ans = min(ans,solver(it));
        red[node] = min(red[node],red[it]);
        blue[node] = min(blue[node],blue[it]);
    }
    //cout << node sp red[node] sp blue[node] sp d[node]<< endl;
    ans = min(ans,red[node]+blue[node]-2*d[node]);
    return ans;
}

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
    int n = N;
    for (int i=0;i<n-1;i++) {
        edges[A[i]].push_back({B[i],D[i]});
        edges[B[i]].push_back({A[i],D[i]});
    }
    dfs(0,0);
    for (int i=1;i<20;i++) {
        for (int j=0;j<n;j++) up[j][i] = up[up[j][i-1]][i-1];
    }
}

long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
  int s = S,t = T;
  vector<int> nodes;
  for (int i=0;i<s;i++) {
      c[X[i]] = 1;
      nodes.push_back(X[i]);
  }
  for (int i=0;i<t;i++) {
      c[Y[i]] = 2;
      nodes.push_back(Y[i]);
  }
  sort(all(nodes),[&](int n1,int n2) {
      return tin[n1] < tin[n2];
  });
  for (int i=0;i<s+t;i++) {
      nodes.push_back(lca(nodes[i],nodes[(i+1)%nodes.size()]));
  }
  sort(all(nodes),[&](int n1,int n2) {
      return tin[n1] < tin[n2];
  });
  nodes.erase(unique(all(nodes)),nodes.end()); 
  stack<int> st;
  st.push(nodes[0]);
  for (int i=1;i<nodes.size();i++) {
      while (!anc(st.top(),nodes[i])) {
          st.pop();
      }
      edg[st.top()].push_back(nodes[i]);
      st.push(nodes[i]);
  }
  int ans = solver(nodes[0]);
  for (auto it : nodes) edg[it].clear(),c[it] = 0;
  return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int32_t, int32_t*, int32_t, int32_t*)':
factories.cpp:92:17: 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]
   92 |   for (int i=1;i<nodes.size();i++) {
      |                ~^~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67