oj.uz

Submission #233660

# Submission time Handle Problem Language Result Execution time Memory
233660 2020-05-21T09:53:54 Z almogwald Factories (JOI14_factories) C++14
33 / 100
 8000 ms 156420 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define forr(i,a,b,c) for(int i=a;i<b;i+=c)
#define fort(i,a,b) forr(i,a,b,1)
#define forn(i,n) fort(i,1,n)
#define fori(i,n) fort(i,0,n)
#define forrb(i,a,b,c) for(int i=b-1;i>=a;i-=c)
#define fortb(i,a,b) forrb(i,a,b,1)
#define fornb(i,n) fortb(i,1,n)
#define forib(i,n) fortb(i,0,n)
using namespace std;
#define into(x) cin >> x;
typedef vector<int> veci;
typedef long long lol;
typedef pair<lol,lol> point;
#define def(x) lol x; into(x)

#define MAX_N          500000
#define logn 19
vector<vector<point>> cons;
lol depth[MAX_N];
int dep[MAX_N];
int f[MAX_N][logn];
void Init(int N, int A[], int B[], int D[]) {
	cons.resize(N);
	fori(i, N - 1) {
		cons[A[i]].push_back({ B[i] , D[i]});
		cons[B[i]].push_back({ A[i] , D[i] });
	}
	f[0][0] = 0;
	dep[0] = 0;
	depth[0] = 0;
	veci visited(N);
	veci stk(1);
	while (!stk.empty()) {
		int cur = stk.back();
		stk.pop_back();
		visited[cur] = 1;
		forn(i, logn) {
			f[cur][i] = f[f[cur][i - 1]][i - 1];
		}
		fori(i, cons[cur].size()) {
			if (visited[cons[cur][i].first] == 0) {
				f[cons[cur][i].first][0] = cur;
				dep[cons[cur][i].first] = dep[cur] + 1;
				depth[cons[cur][i].first] = depth[cur] + cons[cur][i].second;
				stk.push_back(cons[cur][i].first);
			}
		}
	}
}
inline int lca(int l, int r) {
	int k = logn-1;
	while (dep[l] != dep[r]) {
		if (dep[l] + (1 << k) <= dep[r]) {
			r = f[r][k];
		}
		if (dep[r] + (1 << k) <= dep[l]) {
			l = f[l][k];
		}
		k--;
	}
	if (l == r) {
		return l;
	}
	k = logn - 1;
	while (k>=0) {
		if (f[r][k]!= f[l][k]) {
			r = f[r][k];
			l = f[l][k];
		}
		k--;
	}
	return f[l][0];
}
long long Query(int S, int X[], int T, int Y[]) {
	if (S*T*5< cons.size()) {
		lol minmium = 1298719928229189219;
		fori(i, S) {
			fori(j, T) {
				minmium = min(minmium, depth[X[i]] + depth[Y[j]] - 2 * depth[lca(X[i], Y[j])]);
			}
		}
		return minmium;
	} else {
		veci visited(cons.size());
		set<point> stk;
		veci ender(cons.size());
		fori(i, S) {
			stk.insert({ 0,X[i] });
		}
		fori(j, T) {
			ender[Y[j]] = 1;
		}
		while (!stk.empty()) {
			auto it = stk.begin();
			lol dis = it->first;
			int cur = it->second;
			stk.erase(it);
			if (visited[cur]) {
				continue;
			}
			visited[cur] = 1;
			if (ender[cur]) {
				return dis;
			}
			fori(i, cons[cur].size()) {
				stk.insert({ cons[cur][i].second+dis,cons[cur][i].first });
			}
		}
	}
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:6:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,a,b,c) for(int i=a;i<b;i+=c)
                                    ^
factories.cpp:7:21: note: in expansion of macro 'forr'
 #define fort(i,a,b) forr(i,a,b,1)
                     ^~~~
factories.cpp:9:19: note: in expansion of macro 'fort'
 #define fori(i,n) fort(i,0,n)
                   ^~~~
factories.cpp:45:3: note: in expansion of macro 'fori'
   fori(i, cons[cur].size()) {
   ^~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:80:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (S*T*5< cons.size()) {
      ~~~~~^~~~~~~~~~~~~
factories.cpp:6:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,a,b,c) for(int i=a;i<b;i+=c)
                                    ^
factories.cpp:7:21: note: in expansion of macro 'forr'
 #define fort(i,a,b) forr(i,a,b,1)
                     ^~~~
factories.cpp:9:19: note: in expansion of macro 'fort'
 #define fori(i,n) fort(i,0,n)
                   ^~~~
factories.cpp:110:4: note: in expansion of macro 'fori'
    fori(i, cons[cur].size()) {
    ^~~~
factories.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 768 KB Output is correct
2 Correct 921 ms 9720 KB Output is correct
3 Correct 919 ms 9468 KB Output is correct
4 Correct 1148 ms 9972 KB Output is correct
5 Correct 917 ms 9532 KB Output is correct
6 Correct 1883 ms 9960 KB Output is correct
7 Correct 907 ms 9592 KB Output is correct
8 Correct 799 ms 9472 KB Output is correct
9 Correct 913 ms 9616 KB Output is correct
10 Correct 1891 ms 10200 KB Output is correct
11 Correct 901 ms 9336 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 1748 ms 93840 KB Output is correct
3 Correct 3971 ms 94328 KB Output is correct
4 Correct 977 ms 97620 KB Output is correct
5 Correct 4001 ms 94640 KB Output is correct
6 Correct 3097 ms 95092 KB Output is correct
7 Correct 5814 ms 27316 KB Output is correct
8 Correct 909 ms 28828 KB Output is correct
9 Correct 5456 ms 28624 KB Output is correct
10 Correct 3689 ms 28588 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 768 KB Output is correct
2 Correct 921 ms 9720 KB Output is correct
3 Correct 919 ms 9468 KB Output is correct
4 Correct 1148 ms 9972 KB Output is correct
5 Correct 917 ms 9532 KB Output is correct
6 Correct 1883 ms 9960 KB Output is correct
7 Correct 907 ms 9592 KB Output is correct
8 Correct 799 ms 9472 KB Output is correct
9 Correct 913 ms 9616 KB Output is correct
10 Correct 1891 ms 10200 KB Output is correct
11 Correct 901 ms 9336 KB Output is correct
12 Correct 8 ms 512 KB Output is correct
13 Correct 1748 ms 93840 KB Output is correct
14 Correct 3971 ms 94328 KB Output is correct
15 Correct 977 ms 97620 KB Output is correct
16 Correct 4001 ms 94640 KB Output is correct
17 Correct 3097 ms 95092 KB Output is correct
18 Correct 5814 ms 27316 KB Output is correct
19 Correct 909 ms 28828 KB Output is correct
20 Correct 5456 ms 28624 KB Output is correct
21 Correct 3689 ms 28588 KB Output is correct
22 Correct 2507 ms 129324 KB Output is correct
23 Correct 3355 ms 135640 KB Output is correct
24 Correct 2684 ms 130400 KB Output is correct
25 Correct 2760 ms 131556 KB Output is correct
26 Correct 4294 ms 123960 KB Output is correct
27 Correct 3000 ms 130720 KB Output is correct
28 Execution timed out 8066 ms 156420 KB Time limit exceeded
29 Halted 0 ms 0 KB -