#include <bits/stdc++.h>
#define DIMN 70010
#define INF 1000000000
using namespace std;
int lnt , cnt;
int lvl[DIMN] , d[DIMN] , rmq[20][DIMN] , tt[DIMN] , l[DIMN] , up[DIMN];
int logg[DIMN] , poz[DIMN];
map <pair <int,int> , int> mp_max , mp_min;
bitset <DIMN> f;
int lft[DIMN] , r[DIMN];
vector <int> v[DIMN] , w[DIMN];
vector < pair < pair <int , int> , pair <int , int> > > aint[DIMN];
struct idk{
int tip , x , y , val;
} op[DIMN];
pair <int,int> lca (int n , int x , int y){
int dif , p2 , swapped = 0;
/// aducem pe ac nivel
if (lvl[x] < lvl[y]){
swapped = 1;
swap(x , y); /// x e mai jos
}
dif = lvl[x] - lvl[y] - 1;
/// stramosul dif al lui x
while (dif > 0 && x!=0){
x=rmq[logg[dif]][x];
dif=dif-(1<<logg[dif]);
}
/// acum sunt pe acelasi nivel
if (rmq[0][x] == y){ /// y era tatal lui x
if (!swapped)
return make_pair(x , -1);
else return make_pair(-1 , x);
}
if (dif != -1)
x = rmq[0][x];
for (p2 = logg[n] ; p2>=0 ; p2--){
if (rmq[p2][x] != rmq[p2][y]){
x = rmq[p2][x];
y = rmq[p2][y];
}
}
if (!swapped)
return make_pair(x , y);
else return make_pair(y , x);
}
void dfs_lant(int nod){
int i,vecin,ok=0,maxi,fiu;
cnt++;
rmq[0][nod] = tt[nod];
d[nod] = 1;
maxi=0;
fiu=0;
for (i=0;i<v[nod].size();++i){
vecin=v[nod][i];
if (vecin != tt[nod]){
ok=1;
lvl[vecin] = 1 + lvl[nod];
tt[vecin] = nod;
dfs_lant(vecin);
d[nod] += d[vecin];
if (d[vecin]>maxi){
maxi=d[vecin];
fiu=vecin;
}
}
}
if (!ok){ /// frunza
lnt++;
l[nod]=lnt; /// lantul din care apartine
w[lnt].push_back(nod);
}else { /// unim cu poz
w[l[fiu]].push_back(nod);
l[nod]=l[fiu];
for (i=0;i<v[nod].size();++i){
vecin=v[nod][i];
if (vecin!=tt[nod] && vecin!=fiu)
up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului
}
}
v[nod].clear();
}
int cmp_subtask (idk a , idk b){
return a.val > b.val;
}
void build (int lc , int nod , int st , int dr){
int mid = (st + dr) / 2;
if (st == dr){
aint[lc][nod].first.first = INF + 1;
aint[lc][nod].second.first = -1;
return;
}
build (lc , 2 * nod , st , mid);
build (lc , 2 * nod + 1 , mid + 1 , dr);
}
void update_lazy (int lc , int node , int st , int dr , int cod){
if (cod == 1){
if (aint[lc][node].first.second == 0)
return;
if (st == dr){
aint[lc][node].first.second= 0;
return;
}
aint[lc][2 * node].first.first = aint[lc][node].first.first;
aint[lc][2 * node + 1].first.first = aint[lc][node].first.first;
aint[lc][2 * node].first.second = 1;
aint[lc][2 * node + 1].first.second = 1;
aint[lc][node].first.second = 0;
}
else {
if (aint[lc][node].second.second == 0)
return;
if (st == dr){
aint[lc][node].second.second= 0;
return;
}
aint[lc][2 * node].second.first = aint[lc][node].second.first;
aint[lc][2 * node + 1].second.first = aint[lc][node].second.first;
aint[lc][2 * node].second.second = 1;
aint[lc][2 * node + 1].second.second = 1;
aint[lc][node].second.second = 0;
}
}
void update_aint (int lc , int node , int st , int dr , int l , int r , int val , int cod){
int mid;
update_lazy(lc , node , st , dr , cod);
if (l <= st && dr <= r){
if (cod == 1){
aint[lc][node].first.first = val;
aint[lc][node].first.second = 1; /// asta e lazy ul
}
else {
aint[lc][node].second.first = val;
aint[lc][node].second.second = 1; /// asta e lazy ul
}
update_lazy(lc , node , st , dr , cod);
return;
}
mid=((st+dr)>>1);
update_lazy(lc , 2 * node , st , mid , cod);
update_lazy(lc , 2 * node + 1 , mid + 1 , dr , cod);
if (l <= mid){
update_aint( lc , 2 * node , st , mid , l , r , val , cod);
}
if (mid + 1 <= r){
update_aint( lc , 2 * node + 1 , mid + 1 , dr , l , r , val , cod);
}
update_lazy(lc , 2 * node , st , mid , cod);
update_lazy(lc , 2 * node + 1 , mid + 1 , dr , cod);
}
void update (int x , int y , int val , int cod){
if (l[x]!=l[y]){ /// avansam
if (lvl[up[l[x]]]>lvl[up[l[y]]]){
update_aint (l[x] , 1 , 0 , w[l[x]].size() - 1 , 0 , poz[x] , val , cod);
update ( up[l[x]] , y , val , cod);
}
else{
update ( x , up[l[y]] , val , cod);
update_aint( l[y] , 1 , 0 , w[l[y]].size()-1 , 0 , poz[y] , val , cod);
}
}
else {
if (poz[x] <= poz[y])
update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , poz[x] , poz[y] , val , cod);
else
update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , poz[y] , poz[x] , val , cod);
}
}
void query (int lc , int nod , int st , int dr){
int mid = (st + dr) / 2;
update_lazy(lc , nod , st , dr , 1);
update_lazy(lc , nod , st , dr , 2);
if (st == dr){
mp_max[make_pair(tt[w[lc][st]] , w[lc][st])] = aint[lc][nod].first.first;
mp_min[make_pair(tt[w[lc][st]] , w[lc][st])] = aint[lc][nod].second.first;
return;
}
query (lc , 2 * nod , st , mid);
query (lc , 2 * nod + 1 , mid + 1 , dr);
}
int cuplez (int nod){
int i,vecin;
if (f[nod])
return 0;
f[nod]=1;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (!r[vecin]){ /// il cuplez direct
lft[nod]=vecin;
r[vecin]=nod;
return 1;
}
}
f[nod]=1;
/// altfel, caut alta modalitate
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (cuplez (r[vecin])){ /// il pot cupla pe nod cu vecin
lft[nod]=vecin;
r[vecin]=nod;
return 1;
}
}
return 0;
}
int cauta (int x , int q){
int st , dr , mid;
st = 1;
dr = q;
while (st <= dr){
mid = (st + dr)/2;
if (op[mid].val == x){
return mid;
}
else if (op[mid].val < x){
dr = mid - 1;
}
else st = mid + 1;
}
return 0;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , i , x , y , powe , p , vecin , q , nr , ok;
char c;
pair <int,int> z , p1 , p2;
fscanf (fin,"%d",&n);
for (i = 1 ; i < n ; i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
lvl[1] = 1;
dfs_lant (1);
for (i = 2 ; i <= n ; i++)
logg[i] = 1 + logg[i / 2];
for (powe = 1 ; (1 << powe) <= n ; powe++){
for (i = 1 ; i <= n ; i++){
rmq[powe][i] = rmq[powe - 1][rmq[powe - 1][i]];
}
}
/// fiecare nod al catelea e
for (i = 1 ; i <= lnt ; ++i){
reverse(w[i].begin(),w[i].end());
p=0;
for (vector <int> :: iterator j = w[i].begin() ; j != w[i].end() ; j++){
/// pozitia lui din lantul curent
vecin=*j;
poz[vecin]=p;
p++;
}
aint[i].resize(w[i].size() * 5);
build ( i , 1 , 0 , w[i].size() - 1 );
}
fscanf (fin,"%d\n",&q);
for (i = 1 ; i <= q ; i++){
c = fgetc (fin);
fscanf (fin,"%d%d%d\n",&op[i].x,&op[i].y,&op[i].val);
if (c == 'm'){
op[i].tip = 0; /// minim
}
else {
op[i].tip = 1; /// maxim
}
}
sort (op + 1 , op + q + 1 , cmp_subtask);
for (i = 1 ; i <= q ; i++){
if (op[i].tip == 0)
continue;
z = lca (n , op[i].x , op[i].y);
if (-1 != z.first)
update (op[i].x , z.first , op[i].val , 1);
if (-1 != z.second)
update (op[i].y , z.second, op[i].val , 1);
}
for (i = q ; i ; i--){
if (op[i].tip == 1)
continue;
/// pt minime , ordinea crescatoare
z = lca (n , op[i].x , op[i].y);
if (-1 != z.first)
update (op[i].x , z.first , op[i].val , 2);
if (-1 != z.second)
update (op[i].y , z.second, op[i].val , 2);
}
for (i = 1 ; i <= lnt ; i++)
query (i , 1 , 0 , w[i].size() - 1);
/// o muchie are 2 valori : un max si un min
/// eu trb sa aleg pt fiecare daca pun max sau min, asa incat fiecare max sa
/// apara cel putin o data
/// si fiecare min sa apara cel putin o data
/// am vect de operatii deja sortat, fac doar cb
for (i = 1 ; i <= n ; i++)
v[i].clear();
for (i = 2 ; i <= n ; i++){
//printf ("%d %d %d\n" , i , mp_max[make_pair(tt[i] , i)] , mp_min[make_pair(tt[i] , i)] );
if (mp_max[make_pair(tt[i] , i)] != INF + 1){
nr = cauta (mp_max[make_pair(tt[i] , i)] , q);
v[i].push_back(nr);
}
if (mp_min[make_pair(tt[i] , i)] != -1){
nr = cauta (mp_min[make_pair(tt[i] , i)] , q);
v[i].push_back(nr);
}
}
do{
ok=0;
f.reset();
for (i = 1 ; i <= n ; i++){
if (!lft[i])
ok=(ok|cuplez(i));
}
}
while (ok==1);
for (i = 2 ; i <= n ; i++){
if (lft[i]){
fprintf (fout,"%d %d %d\n" , i , tt[i] , op[lft[i]].val);
}
else {
fprintf (fout,"%d %d %d\n", i , tt[i] , mp_max[make_pair(tt[i] , i)]);
}
}
return 0;
}
Compilation message
minmaxtree.cpp: In function 'void dfs_lant(int)':
minmaxtree.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();++i){
~^~~~~~~~~~~~~~
minmaxtree.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();++i){
~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int cuplez(int)':
minmaxtree.cpp:215:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
minmaxtree.cpp:225:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:262:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d",&n);
~~~~~~~^~~~~~~~~~~~~
minmaxtree.cpp:264:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
minmaxtree.cpp:298:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d\n",&q);
~~~~~~~^~~~~~~~~~~~~~~
minmaxtree.cpp:301:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d%d\n",&op[i].x,&op[i].y,&op[i].val);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5376 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5376 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5376 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
342 ms |
35224 KB |
Output is correct |
| 2 |
Correct |
363 ms |
34040 KB |
Output is correct |
| 3 |
Correct |
381 ms |
33784 KB |
Output is correct |
| 4 |
Correct |
330 ms |
35400 KB |
Output is correct |
| 5 |
Correct |
375 ms |
33812 KB |
Output is correct |
| 6 |
Correct |
340 ms |
33632 KB |
Output is correct |
| 7 |
Correct |
298 ms |
33016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
304 ms |
33144 KB |
Output is correct |
| 2 |
Correct |
287 ms |
34308 KB |
Output is correct |
| 3 |
Correct |
266 ms |
34328 KB |
Output is correct |
| 4 |
Correct |
251 ms |
35448 KB |
Output is correct |
| 5 |
Correct |
284 ms |
33400 KB |
Output is correct |
| 6 |
Correct |
285 ms |
33912 KB |
Output is correct |
| 7 |
Correct |
290 ms |
33356 KB |
Output is correct |
| 8 |
Correct |
304 ms |
33528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5376 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5376 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5376 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5376 KB |
Output is correct |
| 5 |
Correct |
342 ms |
35224 KB |
Output is correct |
| 6 |
Correct |
363 ms |
34040 KB |
Output is correct |
| 7 |
Correct |
381 ms |
33784 KB |
Output is correct |
| 8 |
Correct |
330 ms |
35400 KB |
Output is correct |
| 9 |
Correct |
375 ms |
33812 KB |
Output is correct |
| 10 |
Correct |
340 ms |
33632 KB |
Output is correct |
| 11 |
Correct |
298 ms |
33016 KB |
Output is correct |
| 12 |
Correct |
304 ms |
33144 KB |
Output is correct |
| 13 |
Correct |
287 ms |
34308 KB |
Output is correct |
| 14 |
Correct |
266 ms |
34328 KB |
Output is correct |
| 15 |
Correct |
251 ms |
35448 KB |
Output is correct |
| 16 |
Correct |
284 ms |
33400 KB |
Output is correct |
| 17 |
Correct |
285 ms |
33912 KB |
Output is correct |
| 18 |
Correct |
290 ms |
33356 KB |
Output is correct |
| 19 |
Correct |
304 ms |
33528 KB |
Output is correct |
| 20 |
Correct |
351 ms |
35960 KB |
Output is correct |
| 21 |
Correct |
348 ms |
35296 KB |
Output is correct |
| 22 |
Correct |
373 ms |
35436 KB |
Output is correct |
| 23 |
Correct |
323 ms |
35832 KB |
Output is correct |
| 24 |
Correct |
314 ms |
36468 KB |
Output is correct |
| 25 |
Correct |
321 ms |
37884 KB |
Output is correct |
| 26 |
Correct |
316 ms |
37368 KB |
Output is correct |
| 27 |
Correct |
356 ms |
36044 KB |
Output is correct |
| 28 |
Correct |
337 ms |
35448 KB |
Output is correct |
| 29 |
Correct |
353 ms |
35448 KB |
Output is correct |
| 30 |
Correct |
362 ms |
34680 KB |
Output is correct |
| 31 |
Correct |
335 ms |
34936 KB |
Output is correct |
| 32 |
Correct |
347 ms |
35448 KB |
Output is correct |
| 33 |
Correct |
383 ms |
34936 KB |
Output is correct |
| 34 |
Correct |
367 ms |
34804 KB |
Output is correct |
| 35 |
Correct |
363 ms |
34756 KB |
Output is correct |
