Submission #287479

#	Time	Username	Problem	Language	Result	Execution time	Memory
287479		Namnamseo	공장들 (JOI14_factories)	C++17	33 / 100	8042 ms	155160 KiB

factories

#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }

typedef pair<int,ll> pil;

vector<pil> edge[500010];
vector<int> comp[500010];

int par[20][500010];
ll depth[500010];
int d2 [500010];

int n,q;

int tin[500010];
int nt;

void dfs(int x){
	tin[x]=nt++;
	for(auto& yp:edge[x]){
		int y=yp.first; ll d=yp.second;
		if(par[0][x] != y){
			par[0][y] = x;
			depth[y]  = depth[x] + d;
			d2[y]     = d2[x]+1;
			dfs(y);
		}
	}
}

int lca(int a,int b){
	if(d2[a]>d2[b]) swap(a,b);
	int df=d2[b]-d2[a];
	for(int i=18; 0<=i; --i) if(1&(df>>i)) b=par[i][b];
	for(int i=18; 0<=i; --i) if(par[i][a]!=par[i][b])
		a=par[i][a], b=par[i][b];
	if(a!=b) a=par[0][a];
	return a;
}

void sparse(){
	par[0][0] = -1;
	for(int i=1; i<=18; ++i) for(int j=0; j<n; ++j){
		int t=par[i-1][j];
		if(t==-1) par[i][j]=-1;
		else par[i][j]=par[i-1][t];
	}
}

bool isPar(int a,int b){
	if(d2[a]>d2[b]) return false;
	int df=d2[b]-d2[a];
	for(int i=18; 0<=i; --i){
		if(1&(df>>i)) b=par[i][b];
	}
	return a==b;
}

ll dA[500010];
ll dB[500010];

vector<int> hist;

void compress(vector<int>& pts){
	stack<int> stk;
	hist.clear();
	for(int p : pts){
		comp[p].clear();
		while(stk.size() && !isPar(stk.top(), p))
			hist.pb(stk.top()), stk.pop();
		if(stk.size()) comp[stk.top()].pb(p);
		stk.push(p);
	}
	while(stk.size()) hist.pb(stk.top()), stk.pop();
}

ll inf=(1LL<<60);

void Init(int N, int A[], int B[], int D[]) {
    n = N;
	for(int i=0; i<n-1; ++i){
		int a=A[i],b=B[i],d=D[i];
		edge[a].pb({b,d}); edge[b].pb({a,d});
	}
    dfs(0); sparse();
}

long long Query(int A, int X[], int B, int Y[]) {
    vector<int> pa(X, X+A), pb(Y, Y+B), pts;

    for(int x:pa) pts.pb(x);
    for(int x:pb) pts.pb(x);
    auto timecomp = [&](const int& a, const int& b){
        return tin[a]<tin[b];
    };
    sort(all(pts), timecomp);
    int sz=A+B;
    for(int i=1; i<sz; ++i) pts.pb(lca(pts[i-1], pts[i]));
    sort(all(pts), timecomp);
    pts.erase(unique(all(pts)), pts.end());

    compress(pts);

    for(int x:pts) dA[x]=dB[x]=inf;
    for(int x:pa) dA[x]=0;
    for(int x:pb) dB[x]=0;

    ll ans=inf;
    for(int x:hist){
        for(int y:comp[x]){
            dA[x] = min(dA[x], dA[y]+depth[y]-depth[x]);
            dB[x] = min(dB[x], dB[y]+depth[y]-depth[x]);
        }
        ans=min(ans, dA[x]+dB[x]);
    }
    
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void read(int&)':
factories.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 | void read(int& x){ scanf("%d",&x); }
      |                    ~~~~~^~~~~~~~~
factories.cpp: In function 'void read(ll&)':
factories.cpp:11:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 | void read(ll& x){ scanf("%lld",&x); }
      |                   ~~~~~^~~~~~~~~~~

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