#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];
struct idk{
idk *st , *dr;
map <short,int> mp;
idk(){
st = dr = 0;
mp.clear();
}
};
idk *aint[DIMN];
vector <int> v[DIMN] , w[DIMN];
int elem , lnt , curr;
void dfs_lant(int nod , int fth){
int i,vecin,ok=0,maxi,fiu;
tt[nod] = fth;
d[nod] = 1;
maxi=0;
fiu=0;
for (i=0;i<v[nod].size();++i){
vecin=v[nod][i];
if (vecin!=fth){
ok=1;
lvl[vecin] = 1 + lvl[nod];
dfs_lant(vecin , nod);
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!=fth && vecin!=fiu)
up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului
}
}
v[nod].clear();
}
void update_aint (idk *node , int st , int dr , int l , int r , int len , int val , int sens){
int mid , rest;
if (st == dr){
node->mp[len * 100 + curr] += val;
curr++;
return;
}
mid=((st+dr)>>1);
if (sens == -1){
if (l <= mid){
if (node->st == NULL){
node->st = new idk;
}
update_aint(node->st , st , mid , l , r , len , val , sens);
}
if (mid + 1 <= r){
if (node->dr == NULL){
node->dr = new idk;
}
update_aint(node->dr , mid + 1 , dr , l , r , len , val , sens);
}
}
else {
if (mid + 1 <= r){
if (node->dr == NULL){
node->dr = new idk;
}
update_aint(node->dr , mid + 1 , dr , l , r , len , val , sens);
}
if (l <= mid){
if (node->st == NULL){
node->st = new idk;
}
update_aint(node->st , st , mid , l , r , len , val , sens);
}
}
node->mp.clear();
if (node->st != NULL)
for (rest = 0 ; rest < len ; ++rest)
node->mp[len * 100 + rest] += node->st->mp[len * 100 + rest];
if (node->dr != NULL)
for (rest = 0 ; rest < len ; ++rest)
node->mp[len * 100 + rest] += node->dr->mp[len * 100 + rest];
}
void update (int x , int y , int len , int val){
if (l[x]!=l[y]){ /// avansam
if (lvl[up[l[x]]]>lvl[up[l[y]]]){
update_aint (aint[l[x]] , 0 , w[l[x]].size()-1 , 0 , poz[x] , len , val , 1);
update ( up[l[x]] , y , len , val);
}
else{
update ( x , up[l[y]] , len , val );
update_aint( aint[l[y]] , 0 , w[l[y]].size()-1 , 0 , poz[y] , len , val , -1 );
}
}
else {
if (poz[x] <= poz[y])
update_aint( aint[l[x]] , 0 , w[l[x]].size()-1 , poz[x] , poz[y] , len , val , -1 );
else
update_aint( aint[l[x]] , 0 , w[l[x]].size()-1 , poz[y] , poz[x] , len , val , 1 );
}
}
long long query_aint (idk *node , int st , int dr , int px , int py , int t1 , int t2){
int mid , len , rest;
long long sol = 0;
if (px <= st && dr <= py){
for (len = 1 ; len <= 20 ; ++len){
for (rest = 0 ; rest < len ; ++rest){
sol += 1LL * node->mp[len * 100 + rest] * ((t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) - ((t1 - 1) % len >= rest));
}
}
return sol;
}
mid = ((st + dr)>>1);
if (px <= mid && node->st != NULL)
sol = sol + query_aint(node->st , st , mid , px , py , t1 , t2);
if (mid+1 <= py && node->dr != NULL)
sol = sol + query_aint(node->dr , 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(aint[l[x]] , 0 , w[l[x]].size()-1 , 0 , poz[x] , t1 , t2);
else{
return query(x , up[l[y]] , t1 , t2) + query_aint(aint[l[y]] , 0 , w[l[y]].size()-1 , 0 , poz[y] , t1 , t2);
}
}
else{
return query_aint(aint[l[x]] , 0 , w[l[x]].size()-1 , min(poz[x],poz[y]) , max(poz[x],poz[y]) , t1 , t2);
}
}
int adauga (int x , int y){
int nod1 , nod2;
nod1 = x;
nod2 = y;
while (lvl[nod1] > lvl[nod2])
nod1 = tt[nod1];
while (lvl[nod1] < lvl[nod2])
nod2 = tt[nod2];
while (nod1 != nod2){
nod1 = tt[nod1];
nod2 = tt[nod2];
}
return lvl[x] + lvl[y] - 2 * lvl[nod1] + 1;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , i , x , y , tip , k , q , t1 , t2 , p , vecin , len;
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 , 0);
/// 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] = new idk;
}
fscanf (fin,"%d",&k);
for (i = 1 ; i <= k ; ++i){
fscanf (fin,"%d%d",&x,&y);
len = adauga(x , y);
curr = 0;
update(x , y , len , 1);
}
fscanf (fin,"%d",&q);
for (i = 1 ; i <= q ; ++i){
fscanf (fin,"%d",&tip);
if (tip == 1){
fscanf (fin,"%d%d",&x,&y);
len = adauga(x , y);
curr = 0;
update (x , y , len , 1);
}
else if (tip == 2){
fscanf (fin,"%d%d",&x,&y);
len = adauga(x , y);
curr = 0;
update (x , y , len , -1);
}
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_lant(int, int)':
traffickers.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();++i){
~^~~~~~~~~~~~~~
traffickers.cpp:43: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:197: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:199: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:205: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:207: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:209: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:221: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);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
5504 KB |
Output isn't correct |
| 2 |
Incorrect |
73 ms |
12152 KB |
Output isn't correct |
| 3 |
Incorrect |
78 ms |
13304 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1058 ms |
94200 KB |
Output isn't correct |
| 2 |
Incorrect |
1006 ms |
79736 KB |
Output isn't correct |
| 3 |
Incorrect |
1065 ms |
94456 KB |
Output isn't correct |
| 4 |
Incorrect |
1083 ms |
93056 KB |
Output isn't correct |
| 5 |
Incorrect |
1043 ms |
84984 KB |
Output isn't correct |
| 6 |
Incorrect |
1084 ms |
88544 KB |
Output isn't correct |
| 7 |
Incorrect |
1055 ms |
91352 KB |
Output isn't correct |
| 8 |
Incorrect |
1054 ms |
96632 KB |
Output isn't correct |
| 9 |
Incorrect |
963 ms |
73020 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3588 ms |
169116 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3573 ms |
190720 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3596 ms |
200104 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3567 ms |
111744 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3572 ms |
90152 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3572 ms |
200368 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3585 ms |
211332 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3574 ms |
211452 KB |
Time limit exceeded |
