oj.uz

답안 #333254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333254 2020-12-05T05:12:07 Z aloo123 공장들 (JOI14_factories) C++14
33 / 100
 8000 ms 225420 KB 
#include <bits/stdc++.h>
#include "factories.h"


using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using vl = vector<ll>; 
#define mp make_pair
#define f first
#define s second
 
// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define ins insert 
#define pf push_front 
#define pb push_back
 
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const ll INF = 1e18; // not too close to LLONG_MAX

// #define int ll
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!!
const int MAXN = 5e5+5;
const int LOGN = 25;
const int LOGLOGN = 5;
ll n,current_tree = 0;
vector<pl> g[MAXN];
vector<ll> ct[MAXN];
ll best[MAXN],deleted[MAXN];
ll depth[MAXN];
ll par[MAXN],sub[MAXN];
ll dist[LOGN][MAXN];
ll r;
// initally all nodes are red
ll up[MAXN][LOGLOGN];
int tin[MAXN],tout[MAXN];
int timer = 0;
void dfs2(int u,int p){
    tin[u] = ++timer;
    if(p != -1){
        up[u][0] = p;
    }
    trav(v,ct[u]){
        if(v != p){
            dfs2(v,u);
        }
    }
    tout[u] = ++timer;
}
bool is_ans(int u,int v){
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
ll LCA(ll u,ll v){
	// finds LCA in of u and v in the centroid tree
	if(is_ans(u,v)) return u;
    if(is_ans(v,u)) return v;
    ROF(i,0,LOGLOGN){
        if(!is_ans(up[u][i],v)) 
            u = up[u][i];
    }
    return up[u][0];
}
ll compute_dist(ll x,ll y){
	ll lc = depth[LCA(x,y)];
	return dist[lc][x] + dist[lc][y];
}
void find_subtree(ll u,ll p){
	sub[u] = 1;
	current_tree++;
	trav(P,g[u]){
		int v = P.f;
		if(deleted[v] == 0 && v != p){
			find_subtree(v,u);
			sub[u] += sub[v];
		}
	}
}
ll find_centroid(ll u,ll p){
	trav(P,g[u]){
		ll v = P.f;
		if(deleted[v] == 0 && v !=p  && sub[v] > (current_tree / 2)) return find_centroid(v,u);
	}
	return u;
}
void dfs(ll u,ll p,ll lvl,ll dd){
	dist[lvl][u] = dd;
	trav(P,g[u]){
		ll v = P.f;
		ll w = P.s;
		if(deleted[v] == 0 && v != p){
			dfs(v,u,lvl,dd + w);
		}
	}
}
void decompose(ll root,ll p){
	current_tree = 0;

	find_subtree(root,p);
	ll cen = find_centroid(root,p);
	par[cen] = p;
    if(p == -1) r = cen;
	if(p != -1) depth[cen] = depth[p] + 1;
	if(p != -1){
        ct[p].pb(cen);
        ct[cen].pb(p);
    }
    dfs(cen,p,depth[cen],0);
	deleted[cen] = 1;
	trav(P,g[cen]){
		int v = P.f;
		if(deleted[v] == 1) continue;
		decompose(v,cen);
	}
}

ll query(ll u){
	// find the nearest blue node to u
	ll ans = best[u];
	ll x = u;
	u = par[u];
	while(u != -1){
		ans = min(ans,compute_dist(x,u) + best[u]);
		u = par[u];
    }
	return ans;
}
void update(ll u){
	// colour node u to blue
	ll x = u;
	while(u != -1){
		best[u] = min(best[u],compute_dist(u,x));
		u = par[u];
	}
}
void remove_col(ll u){
	// u has to be a blue node
	// remove its colour
	while(u != -1){
		best[u] = INF;
		u = par[u];
	}
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	FOR(i,0,n-1){A[i]++,B[i]++;
		g[A[i]].pb(mp(B[i],D[i]));
		g[B[i]].pb(mp(A[i],D[i]));
	}

	for(int i =1;i<=n;i++) best[i] = INF;
	decompose(1,-1);
    dfs2(r,-1);
    FOR(i,1,LOGLOGN){
        FOR(j,1,n+1){
            if(up[j][i-1] != 0){
                up[j][i] = up[up[j][i-1]][i-1];
            }
        }
    }
}

long long Query(int S, int X[], int T, int Y[]) {
	for(int i =0;i<S;i++) X[i]++;
	for(int i =0;i<T;i++) Y[i]++;
    if(S>T){
        for(int i = 0;i < T;i++){
            update(Y[i]);
        }
        ll ans = INF;
        for(int i = 0;i< S;i++){
            ans = min(ans,query(X[i]));
        }
        for(int i =0;i<T;i++){
            remove_col(Y[i]);
        }
        return ans;
    }
    else{
        for(int i = 0;i < S;i++){
            update(X[i]);
        }
        ll ans = INF;
        for(int i = 0;i< T;i++){
            ans = min(ans,query(Y[i]));
        }
        for(int i =0;i<S;i++){
            remove_col(X[i]);
        }
        return ans;    
    }
}

/* void solve(){
	cin >> n;
	int q;
	cin >> q;
	FOR(i,2,n+1){
		int u,v,w;
		cin >> u >> v >> w;
		u++,v++;
		g[u].pb(mp(v,w));
		g[v].pb(mp(u,w));	
	}
	for(int i =1;i<=n;i++) best[i] = INF;
	decompose(1,-1);
	FOR(i,1,n+1){
		cout << i << " " << par[i] << endl;
	}
	while(q--){
		int s,t;
		cin >> s >> t;
		vl u(s),v(t);
		for(int i =0;i<s;i++) cin >> u[i],u[i]++;
		for(int i =0;i<t;i++) cin >> v[i],v[i]++;
		for(int i = 0;i < t;i++){
			update(v[i]);
		}
		int ans = INF;
		for(int i = 0;i< s;i++){
			ans = min(ans,query(u[i]));
		}
		cout << ans << endl;
		for(int i =0;i<t;i++){
			remove_col(v[i]);
		}
	}
}	
signed main() {
	cin.tie(0)->sync_with_stdio(0);

	// you should actually read the stuff at the bottom
	int t=1;
	// cin >> t;
	while(t--){
		solve();
	}
} */
/* stuff you should look for
	* read the probem 3 more times in case of WA :)
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 24428 KB Output is correct
2 Correct 411 ms 33388 KB Output is correct
3 Correct 494 ms 33388 KB Output is correct
4 Correct 435 ms 33388 KB Output is correct
5 Correct 510 ms 33772 KB Output is correct
6 Correct 297 ms 32876 KB Output is correct
7 Correct 478 ms 33388 KB Output is correct
8 Correct 443 ms 33388 KB Output is correct
9 Correct 524 ms 33820 KB Output is correct
10 Correct 300 ms 32876 KB Output is correct
11 Correct 480 ms 33516 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 24172 KB Output is correct
2 Correct 3315 ms 183660 KB Output is correct
3 Correct 4976 ms 200548 KB Output is correct
4 Correct 1092 ms 130504 KB Output is correct
5 Correct 6387 ms 225420 KB Output is correct
6 Correct 5087 ms 201848 KB Output is correct
7 Correct 2317 ms 67948 KB Output is correct
8 Correct 517 ms 56412 KB Output is correct
9 Correct 2643 ms 71660 KB Output is correct
10 Correct 2254 ms 69100 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 24428 KB Output is correct
2 Correct 411 ms 33388 KB Output is correct
3 Correct 494 ms 33388 KB Output is correct
4 Correct 435 ms 33388 KB Output is correct
5 Correct 510 ms 33772 KB Output is correct
6 Correct 297 ms 32876 KB Output is correct
7 Correct 478 ms 33388 KB Output is correct
8 Correct 443 ms 33388 KB Output is correct
9 Correct 524 ms 33820 KB Output is correct
10 Correct 300 ms 32876 KB Output is correct
11 Correct 480 ms 33516 KB Output is correct
12 Correct 18 ms 24172 KB Output is correct
13 Correct 3315 ms 183660 KB Output is correct
14 Correct 4976 ms 200548 KB Output is correct
15 Correct 1092 ms 130504 KB Output is correct
16 Correct 6387 ms 225420 KB Output is correct
17 Correct 5087 ms 201848 KB Output is correct
18 Correct 2317 ms 67948 KB Output is correct
19 Correct 517 ms 56412 KB Output is correct
20 Correct 2643 ms 71660 KB Output is correct
21 Correct 2254 ms 69100 KB Output is correct
22 Correct 4266 ms 184044 KB Output is correct
23 Correct 4221 ms 188444 KB Output is correct
24 Correct 6711 ms 202512 KB Output is correct
25 Correct 6622 ms 206168 KB Output is correct
26 Correct 7004 ms 202496 KB Output is correct
27 Execution timed out 8086 ms 223632 KB Time limit exceeded
28 Halted 0 ms 0 KB -