oj.uz

Submission #287479

# Submission time Handle Problem Language Result Execution time Memory
287479 2020-08-31T17:20:42 Z Namnamseo Factories (JOI14_factories) C++17
33 / 100
 8000 ms 155160 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 24312 KB Output is correct
2 Correct 1416 ms 33528 KB Output is correct
3 Correct 1508 ms 33092 KB Output is correct
4 Correct 1455 ms 33240 KB Output is correct
5 Correct 1339 ms 33376 KB Output is correct
6 Correct 1130 ms 33016 KB Output is correct
7 Correct 1512 ms 33016 KB Output is correct
8 Correct 1453 ms 33144 KB Output is correct
9 Correct 1359 ms 33384 KB Output is correct
10 Correct 1131 ms 33016 KB Output is correct
11 Correct 1519 ms 33016 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24192 KB Output is correct
2 Correct 3937 ms 115224 KB Output is correct
3 Correct 5063 ms 117860 KB Output is correct
4 Correct 3441 ms 112992 KB Output is correct
5 Correct 4464 ms 147980 KB Output is correct
6 Correct 5393 ms 119700 KB Output is correct
7 Correct 5960 ms 51144 KB Output is correct
8 Correct 3925 ms 64780 KB Output is correct
9 Correct 4656 ms 71160 KB Output is correct
10 Correct 5858 ms 66424 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 24312 KB Output is correct
2 Correct 1416 ms 33528 KB Output is correct
3 Correct 1508 ms 33092 KB Output is correct
4 Correct 1455 ms 33240 KB Output is correct
5 Correct 1339 ms 33376 KB Output is correct
6 Correct 1130 ms 33016 KB Output is correct
7 Correct 1512 ms 33016 KB Output is correct
8 Correct 1453 ms 33144 KB Output is correct
9 Correct 1359 ms 33384 KB Output is correct
10 Correct 1131 ms 33016 KB Output is correct
11 Correct 1519 ms 33016 KB Output is correct
12 Correct 20 ms 24192 KB Output is correct
13 Correct 3937 ms 115224 KB Output is correct
14 Correct 5063 ms 117860 KB Output is correct
15 Correct 3441 ms 112992 KB Output is correct
16 Correct 4464 ms 147980 KB Output is correct
17 Correct 5393 ms 119700 KB Output is correct
18 Correct 5960 ms 51144 KB Output is correct
19 Correct 3925 ms 64780 KB Output is correct
20 Correct 4656 ms 71160 KB Output is correct
21 Correct 5858 ms 66424 KB Output is correct
22 Correct 7038 ms 148164 KB Output is correct
23 Correct 6871 ms 149576 KB Output is correct
24 Correct 7149 ms 153060 KB Output is correct
25 Correct 7175 ms 155160 KB Output is correct
26 Execution timed out 8042 ms 146396 KB Time limit exceeded
27 Halted 0 ms 0 KB -