#include <bits/stdc++.h>
#define DIMN 70010
#define NOKBS 1000010
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[NOKBS];
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].second.second = w[lc][st];
return;
}
build (lc , 2 * nod , st , mid);
build (lc , 2 * nod + 1 , mid + 1 , dr);
aint[nod] = aint[2 * nod];
}
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].second.first;
aint[lc][2 * node].first += aint[lc][node].second.first;
aint[lc][2 * node].second.first += aint[lc][node].second.first;
aint[lc][2 * node].second.first += aint[lc][node].second.first;
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 += val; /// 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);
aint[lc][node] = min( aint[lc][2 * node] , aint[lc][2 * node + 1] );
}
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 );
}
}
pair <int,int> query_aint (int lc, int node , int st , int dr , int px , int py){
int mid;
pair <int,int> sol = make_pair(1000000000 , 0);
update_lazy(lc , node , st , dr);
if (px <= st && dr <= py){
return make_pair(aint[lc][node].first , aint[lc][node].second.second);
}
mid = ((st + dr)>>1);
update_lazy(lc , 2 * node , st , mid);
update_lazy(lc , 2 * node + 1 , mid + 1 , dr);
if (px <= mid)
sol = min( sol , query_aint(lc , 2 * node , st , mid , px , py) );
if (mid+1 <= py)
sol = min( sol , query_aint(lc , 2 * node + 1 , mid + 1 , dr , px , py));
update_lazy(lc , 2 * node , st , mid);
update_lazy(lc , 2 * node + 1 , mid + 1 , dr);
return sol;
}
pair <int,int> query (int x , int y){
if (l[x] != l[y]){ /// avansam
if (lvl[up[l[x]]]>lvl[up[l[y]]]){
return min( query(up[l[x]] , y) , query_aint(l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x]));
}
else{
return min( query(x , up[l[y]]) , query_aint(l[y] , 1 , 0 , w[l[y]].size()-1 , 0 , poz[y]));
}
}
else{
return query_aint(l[x] , 1 , 0 , w[l[x]].size()-1 , min(poz[x],poz[y]) , max(poz[x],poz[y]));
}
}
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
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 , 1);
if (-1 != z.second)
update (op[i].y , z.second, 1);
}
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);
p1 = p2 = make_pair(1000000000 , 0);
if (-1 != z.first)
p1 = query (op[i].x , z.first);
if (-1 != z.second)
p2 = query (op[i].y , z.second);
if (p1.first <= p2.first)
node = p1.second;
else node = p2.second;
mp[make_pair(node , tt[node])] = op[i].val;
z = lca (n , op[i].x , op[i].y);
if (-1 != z.first)
update (op[i].x , z.first , -1);
if (-1 != z.second)
update (op[i].y , z.second, -1);
}
for (i = 2 ; i <= n ; i++){
if (mp[make_pair(i , tt[i])] == 0)
fprintf (fout,"%d %d 1\n" , i , tt[i]);
else fprintf (fout,"%d %d %d\n" , i , tt[i] , mp[make_pair(i , tt[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:211: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:213: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:247: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:251: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);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
27136 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
374 ms |
50164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
89 ms |
42744 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
27136 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
