#include<bits/stdc++.h>
using namespace std;
int N, M, ans[70009], lev[70009], t[70009][18], lft[70009], rgt[70009], x[70009], y[70009], a[70009], b[70009], c[70009], ap[70009];
vector < pair < int, int > > v[70009], h[70009];
void dfs (int nod, int tata)
{
for (int j=1; (1 << j) <= lev[nod]; j++)
t[nod][j] = t[t[nod][j - 1]][j - 1];
for (auto it : v[nod])
if (it.first != tata)
lev[it.first] = lev[nod] + 1, t[it.first][0] = nod, dfs (it.first, nod);
}
void moveUp (int &x, int k)
{
for (int i=0; (1 << i) <= k; i++)
if (k & (1 << i))
x = t[x][i];
}
int lca (int x, int y)
{
if (lev[x] > lev[y]) swap (x, y);
moveUp (y, lev[y] - lev[x]);
if (x == y) return x;
int lg = 0;
while ((2 << lg) <= lev[x])
lg ++;
for (int i=lg; i>=0; i--)
if (t[x][i] != t[y][i] && t[x][i] != 0)
x = t[x][i], y = t[y][i];
return t[x][0];
}
int fa[70009], upMost[70009];
int tata (int i)
{
if (fa[i] == i) return i;
return fa[i] = tata (fa[i]);
}
void unite (int i, int j)
{
i = tata (i);
j = tata (j);
fa[i] = j;
if (lev[upMost[j]] > lev[upMost[i]])
upMost[j] = upMost[i];
}
void paint (int jos, int sus, int culoare, int col[])
{
jos = upMost[tata (jos)];
while (lev[jos] > lev[sus])
{
col[jos] = culoare;
unite (jos, t[jos][0]);
jos = upMost[tata (jos)];
}
}
void colorNodes (vector < pair < int, int > > ops, int col[])
{
for (int i=1; i<=N; i++)
col[i] = 0, fa[i] = i, upMost[i] = i;
for (auto o : ops)
{
int i = o.second, d = lca (a[i], b[i]);
paint (a[i], d, i, col);
paint (b[i], d, i, col);
}
}
void init ()
{
vector < pair < int, int > > mi, ma;
scanf ("%d", &N);
for (int i=1; i<N; i++)
{
scanf ("%d %d", &x[i], &y[i]);
v[x[i]].push_back ({y[i], i});
v[y[i]].push_back ({x[i], i});
}
dfs (1, -1);
scanf ("%d\n", &M);
for (int i=1; i<=M; i++)
{
char type;
scanf ("%c %d %d %d\n", &type, &a[i], &b[i], &c[i]);
if (type == 'm') mi.push_back ({c[i], i});
else ma.push_back ({c[i], i});
}
sort (mi.begin (), mi.end ());
reverse (mi.begin (), mi.end ());
sort (ma.begin (), ma.end ());
colorNodes (mi, lft);
colorNodes (ma, rgt);
}
void match (int edge, int op)
{
ans[edge] = c[op];
}
int X, Y, E;
void findSpanningTree (int nod)
{
ap[nod] = 2;
for (auto it : h[nod])
if (ap[it.first] == 0)
fa[it.first] = it.second, findSpanningTree (it.first);
else
if (ap[it.first] == 2 && it.second != fa[nod])
X = it.first, Y = nod, E = it.second;
}
void finalDfs (int nod)
{
ap[nod] = 1;
for (auto it : h[nod])
if (it.second != E && ap[it.first] == 2)
match (it.second, it.first), finalDfs (it.first);
}
void reliefStress (int requirement)
{
for (auto e : h[requirement])
{
int other = e.first;
if (ap[other] == 0)
ap[other] = 1, match (e.second, other), reliefStress (other);
}
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
init ();
for (int i=2; i<=N; i++)
if (lft[i] > 0 && rgt[i] > 0)
{
h[lft[i]].push_back ({rgt[i], i});
h[rgt[i]].push_back ({lft[i], i});
}
for (int i=2; i<=N; i++)
if (lft[i] == 0 || rgt[i] == 0)
{
if (lft[i] + rgt[i] == 0) continue;
if (ap[lft[i]] || ap[rgt[i]]) continue;
if (lft[i] > 0) match (i, lft[i]), ap[lft[i]] = 1, reliefStress (lft[i]);
else match (i, rgt[i]), ap[rgt[i]] = 1, reliefStress (rgt[i]);
}
for (int i=1; i<=M; i++)
if (ap[i] == 0)
{
X = Y = -1;
fa[i] = -1, findSpanningTree (i);
assert (X != -1);
match (E, X);
finalDfs (X);///omitting the edge X, Y which I keep for satisfying X
}
assert (ap[0] == 0);
for (int i=2; i<=N; i++)
{
if (ans[i] == 0) ans[i] = 1;
printf ("%d %d %d\n", t[i][0], i, ans[i]);
}
return 0;
}
Compilation message
minmaxtree.cpp: In function 'void init()':
minmaxtree.cpp:80:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &N);
~~~~~~^~~~~~~~~~
minmaxtree.cpp:83:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &x[i], &y[i]);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:88:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d\n", &M);
~~~~~~^~~~~~~~~~~~
minmaxtree.cpp:92:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%c %d %d %d\n", &type, &a[i], &b[i], &c[i]);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3576 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3688 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3720 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
17780 KB |
Output is correct |
| 2 |
Correct |
197 ms |
17780 KB |
Output is correct |
| 3 |
Correct |
186 ms |
17780 KB |
Output is correct |
| 4 |
Correct |
230 ms |
18256 KB |
Output is correct |
| 5 |
Correct |
178 ms |
18256 KB |
Output is correct |
| 6 |
Correct |
165 ms |
18256 KB |
Output is correct |
| 7 |
Correct |
157 ms |
18256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
110 ms |
18256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3576 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3688 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3720 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3796 KB |
Output is correct |
| 5 |
Correct |
210 ms |
17780 KB |
Output is correct |
| 6 |
Correct |
197 ms |
17780 KB |
Output is correct |
| 7 |
Correct |
186 ms |
17780 KB |
Output is correct |
| 8 |
Correct |
230 ms |
18256 KB |
Output is correct |
| 9 |
Correct |
178 ms |
18256 KB |
Output is correct |
| 10 |
Correct |
165 ms |
18256 KB |
Output is correct |
| 11 |
Correct |
157 ms |
18256 KB |
Output is correct |
| 12 |
Incorrect |
110 ms |
18256 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
