oj.uz

답안 #61467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61467 2018-07-26T04:48:04 Z ainta(#1774) Min-max tree (BOI18_minmaxtree) C++11
29 / 100
 483 ms 39220 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);
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8952 KB Output is correct
2 Correct 10 ms 9060 KB Output is correct
3 Correct 12 ms 9060 KB Output is correct
4 Correct 12 ms 9096 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 483 ms 37952 KB Output is correct
2 Correct 410 ms 37952 KB Output is correct
3 Correct 397 ms 37952 KB Output is correct
4 Correct 381 ms 39220 KB Output is correct
5 Correct 459 ms 39220 KB Output is correct
6 Correct 420 ms 39220 KB Output is correct
7 Correct 451 ms 39220 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 305 ms 39220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8952 KB Output is correct
2 Correct 10 ms 9060 KB Output is correct
3 Correct 12 ms 9060 KB Output is correct
4 Correct 12 ms 9096 KB Output is correct
5 Correct 483 ms 37952 KB Output is correct
6 Correct 410 ms 37952 KB Output is correct
7 Correct 397 ms 37952 KB Output is correct
8 Correct 381 ms 39220 KB Output is correct
9 Correct 459 ms 39220 KB Output is correct
10 Correct 420 ms 39220 KB Output is correct
11 Correct 451 ms 39220 KB Output is correct
12 Incorrect 305 ms 39220 KB Output isn't correct
13 Halted 0 ms 0 KB -