| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 61458 |
2018-07-26T04:40:18 Z |
ainta(#1774) |
Min-max tree (BOI18_minmaxtree) |
C++11 |
|
414 ms |
79024 KB |
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 70100
#define SZ 131072
using namespace std;
vector<int>E[N_], Ch[N_], G[N_+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, 0, x);
}
else {
Put(b, e, x, INF);
}
}
Tree Get(int a) {
a += SZ;
Tree r = { 0,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) {
int t = lower_bound(X + 1, X + n + 1, a) - X;
if (t < 1 || t > n)return 0;
return t;
}
void Add(int a, int b) {
G[a].push_back(b);
G[b].push_back(a);
Deg[a]++;
Deg[b]++;
}
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].Mx = 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++)if (Res[i] == 0)Res[i] = 1;
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:157: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:165:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
minmaxtree.cpp:168: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:174:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
~~~~~^~~~~~~~~~
minmaxtree.cpp:178:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", pp);
~~~~~^~~~~~~~~~
minmaxtree.cpp:179: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
12280 KB |
Output is correct |
| 2 |
Correct |
15 ms |
12516 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
12516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
414 ms |
79024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
208 ms |
79024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
12280 KB |
Output is correct |
| 2 |
Correct |
15 ms |
12516 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
12516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
