oj.uz

Submission #61470

# Submission time Handle Problem Language Result Execution time Memory
61470 2018-07-26T04:53:04 Z ainta(#1774) Min-max tree (BOI18_minmaxtree) C++11
58 / 100
 719 ms 74256 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 70100
#define SZ 131072
using namespace std;
vector<int>E[N_], Ch[N_];
int C[N_], Heavy[N_], Num[N_], cnt, Ed[N_], ppp[N_], Dep[N_], par[N_][20], INF = (1e9)+10;
int n, m, X[N_], Deg[N_+N_], Q[N_], Res[N_];
void DFS(int a, int pp) {
	C[a] = 1;
	par[a][0] = pp;
	for (int i = 0; i < 17; i++)par[a][i+1] = par[par[a][i]][i];
	for (auto &x : E[a]) {
		if (x == pp)continue;
		Dep[x] = Dep[a] + 1;
		DFS(x, a);
		Ch[a].push_back(x);
		C[a] += C[x];
	}
	int pv = 0;
	for (auto &x : Ch[a]) {
		if (C[pv] < C[x])pv = x;
	}
	Heavy[a] = pv;
}
void DFS2(int a, int pp) {
	Num[a] = ++cnt;
	ppp[a] = pp;
	if (Heavy[a])DFS2(Heavy[a], pp);
	for (auto &x : Ch[a]) {
		if (x != Heavy[a])DFS2(x, x);
	}
	Ed[a] = cnt;
}
struct point {
	int a, b, x, ck;
}w[N_];
int LCA(int a, int b) {
	if (Dep[a] < Dep[b])return LCA(b, a);
	int d = Dep[a] - Dep[b], i = 0;
	while (d) {
		if (d & 1)a = par[a][i];
		d >>= 1; i++;
	}
	for (i = 17; i >= 0; i--)if (par[a][i] != par[b][i])a = par[a][i], b = par[b][i];
	if (a != b)a = par[a][0];
	return a;
}
struct Tree {
	int Mn, Mx;
}IT[SZ+SZ];
void UDT(int nd, int Mn, int Mx) {
	IT[nd].Mn = max(IT[nd].Mn, Mn);
	IT[nd].Mx = min(IT[nd].Mx, Mx);
}
void Put(int b, int e, int Mn, int Mx) {
	b += SZ, e += SZ;
	while (b <= e) {
		if (b & 1)UDT(b, Mn, Mx);
		if (!(e & 1))UDT(e, Mn, Mx);
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
}
void Put2(int b, int e, int x, int ck) {
	if (ck == 1) {
		Put(b, e, -INF, x);
	}
	else {
		Put(b, e, x, INF);
	}
}
Tree Get(int a) {
	a += SZ;
	Tree r = { -INF,INF };
	while (a) {
		r.Mn = max(r.Mn, IT[a].Mn);
		r.Mx = min(r.Mx, IT[a].Mx);
		a >>= 1;
	}
	return r;
}
void Go(int a, int pp, int x, int ck) {
	if (Dep[a] <= Dep[pp])return;
	int t = ppp[a];
	if (Dep[t] <= Dep[pp]) {
		Put2(Num[pp] + 1, Num[a], x, ck);
		return;
	}
	Put2(Num[t], Num[a], x, ck);
	Go(par[t][0], pp, x, ck);
}
int Ord(int a) {
	if (a <= 0 || a > 1e9)return 0;
	int t = lower_bound(X + 1, X + m + 1, a) - X;
	return t;
}

class MaxFlow {
public:
	struct Edge {
		int b, e, f;
	}E[501000];
	vector<int>G[N_+N_];
	int Level[N_ + N_], Q[N_ + N_], PV[N_ + N_], source, sink, n, flow, EC;
	void init(int N, int S, int T) {
		n = N, flow = EC = 0;
		source = S, sink = T;
	}
	void Add_Edge(int a, int b, int f) {
		G[a].push_back(EC);
		G[b].push_back(EC + 1);
		E[EC++] = { a,b,f };
		E[EC++] = { b,a,0 };
	}
	bool GetLevel() {
		int i;
		for (i = 1; i <= n; i++)Level[i] = -1;
		int head = 0, tail = 0;
		Q[++tail] = source, Level[source] = 0;
		while (head < tail) {
			int x = Q[++head];
			for (auto &y : G[x]) {
				if (E[y].f && Level[E[y].e] == -1) {
					Q[++tail] = E[y].e;
					Level[E[y].e] = Level[x] + 1;
				}
			}
		}
		return Level[sink] != -1;
	}
	int BlockFlow(int a, int f) {
		if (a == sink)return f;
		for (int &i = PV[a]; i >= 0; i--) {
			int x = G[a][i];
			if (E[x].f && Level[E[x].e] == Level[a] + 1) {
				int t = BlockFlow(E[x].e, min(f, E[x].f));
				if (t) {
					E[x].f -= t;
					E[x ^ 1].f += t;
					return t;
				}
			}
		}
		return 0;
	}
	void Dinic() {
		int t;
		while (GetLevel()) {
			for (int i = 1; i <= n; i++)PV[i] = G[i].size() - 1;
			while (t = BlockFlow(source, INF)) flow += t;
		}
	}

}G1;

int main() {
	int i, a, b;
	scanf("%d", &n);
	for (i = 1; i < SZ + SZ; i++)IT[i] = { -INF,INF };
	for (i = 1; i < n; i++) {
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	DFS(1, 0);
	DFS2(1, 1);
	scanf("%d", &m);
	for (i = 1; i <= m; i++) {
		char pp[3];
		int x, ck;
		scanf("%s", pp);
		scanf("%d%d%d", &a, &b, &x);
		X[i] = x;
		if (pp[0] == 'M')ck = 1;
		else ck = 2;
		w[i] = { a,b,x,ck };
		int l = LCA(a, b);
		Go(a, l, x, ck);
		Go(b, l, x, ck);
	}
	sort(X + 1, X + m + 1);
	G1.init(n + m + 1, 1, n + m + 1);
	for (i = 2; i <= n; i++) {
		Tree t = Get(Num[i]);
		int b = Ord(t.Mn);
		int e = Ord(t.Mx);
		Res[i] = t.Mn;
		if (b)G1.Add_Edge(i, n + b, 1);
		if (e)G1.Add_Edge(i, n + e, 1);
	}
	for (i = 2; i <= n; i++) {
		G1.Add_Edge(G1.source, i, 1);
	}
	for (i = 1; i <= m; i++) {
		G1.Add_Edge(n+i, G1.sink, 1);
	}
	G1.Dinic();
	for (i = n+1; i <= n+m; i++) {
		for (auto &t : G1.G[i]) {
			if (G1.E[t].f && G1.E[t].e<=n) {
				Res[G1.E[t].e] = X[i - n];
			}
		}
	}
	for (i = 2; i <= n; i++) {
		printf("%d %d %d\n", par[i][0], i, Res[i]);
	}
}

Compilation message

minmaxtree.cpp: In member function 'void MaxFlow::Dinic()':
minmaxtree.cpp:151:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    while (t = BlockFlow(source, INF)) flow += t;
           ~~^~~~~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
minmaxtree.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
minmaxtree.cpp:172:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", pp);
   ~~~~~^~~~~~~~~~
minmaxtree.cpp:173:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8952 KB Output is correct
2 Correct 12 ms 9188 KB Output is correct
3 Correct 12 ms 9188 KB Output is correct
4 Correct 11 ms 9188 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 37964 KB Output is correct
2 Correct 327 ms 37964 KB Output is correct
3 Correct 417 ms 37964 KB Output is correct
4 Correct 544 ms 39444 KB Output is correct
5 Correct 516 ms 39444 KB Output is correct
6 Correct 364 ms 39444 KB Output is correct
7 Correct 411 ms 39444 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 39444 KB Output is correct
2 Correct 272 ms 39444 KB Output is correct
3 Correct 336 ms 39444 KB Output is correct
4 Correct 296 ms 39444 KB Output is correct
5 Correct 360 ms 39444 KB Output is correct
6 Correct 320 ms 39444 KB Output is correct
7 Correct 366 ms 39444 KB Output is correct
8 Correct 453 ms 39444 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8952 KB Output is correct
2 Correct 12 ms 9188 KB Output is correct
3 Correct 12 ms 9188 KB Output is correct
4 Correct 11 ms 9188 KB Output is correct
5 Correct 415 ms 37964 KB Output is correct
6 Correct 327 ms 37964 KB Output is correct
7 Correct 417 ms 37964 KB Output is correct
8 Correct 544 ms 39444 KB Output is correct
9 Correct 516 ms 39444 KB Output is correct
10 Correct 364 ms 39444 KB Output is correct
11 Correct 411 ms 39444 KB Output is correct
12 Correct 365 ms 39444 KB Output is correct
13 Correct 272 ms 39444 KB Output is correct
14 Correct 336 ms 39444 KB Output is correct
15 Correct 296 ms 39444 KB Output is correct
16 Correct 360 ms 39444 KB Output is correct
17 Correct 320 ms 39444 KB Output is correct
18 Correct 366 ms 39444 KB Output is correct
19 Correct 453 ms 39444 KB Output is correct
20 Correct 719 ms 39444 KB Output is correct
21 Correct 361 ms 39444 KB Output is correct
22 Correct 534 ms 39444 KB Output is correct
23 Correct 566 ms 39444 KB Output is correct
24 Runtime error 329 ms 74256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -