#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int tt[DIMN] , lvl[DIMN] , f[DIMN];
int up[DIMN] , l[DIMN] , d[DIMN] , poz[DIMN] , idx_aint[DIMN];
vector < map <int,int> > aint[DIMN];
vector <int> v[DIMN] , w[DIMN];
multiset <pair <int,pair <int,int> > > stare[DIMN];
int elem , lnt;
void dfs (int nod , int fth , int nivel){
int i , vecin;
tt[nod] = fth;
lvl[nod] = nivel;
d[nod] = 1;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != fth){
dfs(vecin , nod , nivel + 1);
d[nod] += d[vecin];
}
}
}
void dfs_lant(int nod){
int i,vecin,ok=0,maxi,fiu;
maxi=0;
fiu=0;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (vecin!=tt[nod]){
ok=1;
dfs_lant(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
}
}
}
void build_aint (int lant , int p , int st , int dr){
int mid = (st + dr)/2;
if (st == dr){
idx_aint[w[lant][st]] = p;
return;
}
build_aint(lant , 2 * p , st , mid);
build_aint(lant , 2 * p + 1 , mid + 1 , dr);
}
void update_aint (int lant , int p , int st , int dr , int l , int r){
int mid , len , rest;
if (st == dr){
return;
}
mid=(st+dr)/2;
if (l <= mid)
update_aint(lant , 2 * p , st , mid , l , r);
if (mid + 1 <= r)
update_aint(lant , 2 * p + 1 , mid + 1 , dr , l , r);
for (len = 1 ; len <= 20 ; len++){
for (rest = 0 ; rest < len ; rest++)
aint[lant][p][len * 100 + rest] = aint[lant][2 * p][len * 100 + rest] + aint[lant][2 * p + 1][len * 100 + rest];
}
}
void update (int x , int y){
if (l[x]!=l[y]){ /// avansam
if (lvl[up[l[x]]]>lvl[up[l[y]]]){
update ( up[l[x]] , y );
update_aint (l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x] );
}
else{
update ( x , up[l[y]] );
update_aint( l[y] , 1 , 0 , w[l[y]].size()-1 , 0 , poz[y] );
}
}
else {
update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , min(poz[x],poz[y]) , max(poz[x],poz[y]) );
}
}
long long query_aint (int lant , int p , int st , int dr , int px , int py , int t1 , int t2){
int sol=0 , mid , len , rest;
if (px <= st && dr <= py){
for (len = 1 ; len <= 20 ; len ++){
for (rest = 0 ; rest < len ; rest++){
//if (aint[lant][p][len * 100 + rest])
// printf ("%d %d %d\n" , len , rest ,aint[lant][p][len * 100 + rest] );
sol += aint[lant][p][len * 100 + rest] * ( (t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) - ((t1 - 1) % len >= rest));
}
}
return sol;
}
mid = (st + dr)/2;
if (px <= mid)
sol = sol + query_aint(lant , 2 * p , st , mid , px , py , t1 , t2);
if (mid+1 <= py)
sol = sol + query_aint(lant , 2 * p + 1 , mid + 1 , dr , px , py , t1 , t2);
return sol;
}
long long query (int x , int y , int t1 , int t2){
if (l[x] != l[y]){ /// avansam
if (lvl[up[l[x]]]>lvl[up[l[y]]])
return query(up[l[x]] , y , t1 , t2) + query_aint(l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x] , t1 , t2);
else{
return query(x , up[l[y]] , t1 , t2) + query_aint(l[y] , 1 , 0 , w[l[y]].size()-1 , 0 , poz[y] , t1 , t2);
}
}
else{
return query_aint(l[x] , 1 , 0 , w[l[x]].size()-1 , min(poz[x],poz[y]) , max(poz[x],poz[y]) , t1 , t2);
}
}
void adauga (int x , int y , int val , int op){
int lca , nod , poz , len , i;
nod = x;
for (i = 0 ; i < 20 ; i++){
f[nod] = op;
nod = tt[nod];
}
nod = y;
for (i = 0 ; i < 20 ; i++){
if (f[nod] == op){
lca = nod;
break;
}
f[nod] = op;
nod = tt[nod];
}
len = lvl[x] + lvl[y] - 2 * lvl[lca] + 1;
nod = x;
poz = 0;
while (nod != tt[lca]){
aint[l[nod]][idx_aint[nod]][len * 100 + poz] += val;
poz++;
nod = tt[nod];
}
nod = y;
poz = len - 1;
while (nod != lca){
aint[l[nod]][idx_aint[nod]][len * 100 + poz] += val;
poz--;
nod = tt[nod];
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , i , x , y , tip , k , q , t1 , t2 , p , vecin;
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);
}
dfs(1 , 0 , 1);
dfs_lant(1);
/// 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_aint(i , 1 , 0 , w[i].size() - 1);
}
fscanf (fin,"%d",&k);
int op = 1;
for (i = 1 ; i <= k ; i++){
fscanf (fin,"%d%d",&x,&y);
adauga(x , y , 1 , ++op);
update(x , y);
}
fscanf (fin,"%d",&q);
for (i = 1 ; i <= q ; i++){
fscanf (fin,"%d",&tip);
if (tip == 1){
fscanf (fin,"%d%d",&x,&y);
adauga(x , y , 1 , ++op);
update (x , y);
}
else if (tip == 2){
fscanf (fin,"%d%d",&x,&y);
adauga(x , y , -1 , ++op);
update (x , y);
}
else {
fscanf (fin,"%d%d%d%d",&x,&y,&t1,&t2);
fprintf (fout,"%lld\n",query (x , y , t1 , t2));
}
}
return 0;
}
Compilation message
traffickers.cpp: In function 'void dfs(int, int, int)':
traffickers.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
traffickers.cpp: In function 'void dfs_lant(int)':
traffickers.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
traffickers.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
traffickers.cpp: In function 'int main()':
traffickers.cpp:173:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d",&n);
~~~~~~~^~~~~~~~~~~~~
traffickers.cpp:175: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);
~~~~~~~^~~~~~~~~~~~~~~~~~
traffickers.cpp:198:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d",&k);
~~~~~~~^~~~~~~~~~~~~
traffickers.cpp:201: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);
~~~~~~~^~~~~~~~~~~~~~~~~~
traffickers.cpp:206:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d",&q);
~~~~~~~^~~~~~~~~~~~~
traffickers.cpp:208:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d",&tip);
~~~~~~~^~~~~~~~~~~~~~~
traffickers.cpp:210:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
traffickers.cpp:215:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
traffickers.cpp:220:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d%d%d",&x,&y,&t1,&t2);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp: In function 'void adauga(int, int, int, int)':
traffickers.cpp:134:9: warning: 'lca' may be used uninitialized in this function [-Wmaybe-uninitialized]
int lca , nod , poz , len , i;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
13056 KB |
Output is correct |
| 2 |
Correct |
241 ms |
32120 KB |
Output is correct |
| 3 |
Correct |
194 ms |
26364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2674 ms |
176208 KB |
Output isn't correct |
| 2 |
Incorrect |
2299 ms |
139984 KB |
Output isn't correct |
| 3 |
Incorrect |
2772 ms |
196680 KB |
Output isn't correct |
| 4 |
Incorrect |
2590 ms |
168304 KB |
Output isn't correct |
| 5 |
Incorrect |
2445 ms |
155396 KB |
Output isn't correct |
| 6 |
Incorrect |
2527 ms |
161132 KB |
Output isn't correct |
| 7 |
Incorrect |
2550 ms |
166248 KB |
Output isn't correct |
| 8 |
Incorrect |
2828 ms |
206284 KB |
Output isn't correct |
| 9 |
Incorrect |
2879 ms |
213272 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3562 ms |
425480 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3610 ms |
516460 KB |
Time limit exceeded |
| 3 |
Runtime error |
2617 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Execution timed out |
3586 ms |
336196 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3591 ms |
312708 KB |
Time limit exceeded |
| 6 |
Runtime error |
2852 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
2385 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
2353 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
