#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;
vector <int> v[DIMN] , w[DIMN];
vector <pair <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 = INF;
aint[lc][nod].second.second = w[lc][st];
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){
if (aint[lc][node].second.first == 0)
return;
if (st == dr){
aint[lc][node].second.first= 0;
return;
}
aint[lc][2 * node].first = aint[lc][node].first;
aint[lc][2 * node + 1].first = aint[lc][node].first;
aint[lc][2 * node].second.first = 1;
aint[lc][2 * node + 1].second.first = 1;
aint[lc][node].second.first = 0;
}
void update_aint (int lc , int node , int st , int dr , int l , int r , int val){
int mid;
update_lazy(lc , node , st , dr);
if (l <= st && dr <= r){
aint[lc][node].first = val;
aint[lc][node].second.first = 1; /// asta e lazy ul
update_lazy(lc , node , st , dr);
return;
}
mid=((st+dr)>>1);
update_lazy(lc , 2 * node , st , mid);
update_lazy(lc , 2 * node + 1 , mid + 1 , dr);
if (l <= mid){
update_aint( lc , 2 * node , st , mid , l , r , val);
}
if (mid + 1 <= r){
update_aint( lc , 2 * node + 1 , mid + 1 , dr , l , r , val);
}
update_lazy(lc , 2 * node , st , mid);
update_lazy(lc , 2 * node + 1 , mid + 1 , dr);
}
void update (int x , int y , int val){
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);
update ( up[l[x]] , y , val);
}
else{
update ( x , up[l[y]] , val );
update_aint( l[y] , 1 , 0 , w[l[y]].size()-1 , 0 , poz[y] , val );
}
}
else {
if (poz[x] <= poz[y])
update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , poz[x] , poz[y] , val );
else
update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , poz[y] , poz[x] , val );
}
}
void query (int lc , int nod , int st , int dr){
int mid = (st + dr) / 2;
//if (lc == 3 && st == 6 && dr == 7){
// printf ("%d ",aint[lc][2 * nod].first);
//}
update_lazy(lc , nod , st , dr);
if (st == dr){
mp[make_pair(tt[w[lc][st]] , w[lc][st])] = aint[lc][nod].first;
return;
}
query (lc , 2 * nod , st , mid);
query (lc , 2 * nod + 1 , mid + 1 , dr);
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , i , x , y , powe , p , ok , vecin , q , node;
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);
ok = 1;
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
//ok = 0;
}
else {
op[i].tip = 1; /// maxim
}
}
if (ok == 1){ /// ai doar maxime
sort (op + 1 , op + q + 1 , cmp_subtask);
for (i = 1 ; i <= q ; i++){
if (op[i].tip == 0)
continue;
//if (op[i].x == 11 && op[i].y == 14)
// printf ("a");
z = lca (n , op[i].x , op[i].y);
if (-1 != z.first)
update (op[i].x , z.first , op[i].val);
if (-1 != z.second)
update (op[i].y , z.second, op[i].val);
}
for (i = 1 ; i <= lnt ; i++)
query (i , 1 , 0 , w[i].size() - 1);
for (i = 2 ; i <= n ; i++){
if (mp[make_pair(tt[i] , i)] == 0)
fprintf (fout,"%d %d 1\n" , i , tt[i]);
else fprintf (fout,"%d %d %d\n" , i , tt[i] , mp[make_pair(tt[i] , i)]);
}
}
return 0;
}
Compilation message
minmaxtree.cpp: In function 'void dfs_lant(int)':
minmaxtree.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();++i){
~^~~~~~~~~~~~~~
minmaxtree.cpp:77:19: 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:187:53: warning: unused variable 'node' [-Wunused-variable]
int n , i , x , y , powe , p , ok , vecin , q , node;
^~~~
minmaxtree.cpp:190: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:192: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:226: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:230: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 |
Incorrect |
7 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
28272 KB |
Output is correct |
| 2 |
Correct |
311 ms |
29560 KB |
Output is correct |
| 3 |
Correct |
240 ms |
29304 KB |
Output is correct |
| 4 |
Correct |
231 ms |
30836 KB |
Output is correct |
| 5 |
Correct |
228 ms |
29304 KB |
Output is correct |
| 6 |
Correct |
207 ms |
29048 KB |
Output is correct |
| 7 |
Correct |
184 ms |
28408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
202 ms |
26872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
