#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int eul[2*DIMN] , first[DIMN] , nv[2*DIMN] , tt[DIMN] , nivel[DIMN] , logg[2*DIMN];
int rmq[20][2*DIMN];
vector <int> v[DIMN];
set <pair <int,int> > stare[DIMN];
int elem;
void dfs (int nod , int fth , int lvl){
int i , vecin;
eul[++elem] = nod;
first[nod] = elem;
nv[elem] = lvl;
tt[nod] = fth;
nivel[nod] = lvl;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != fth){
dfs(vecin , nod , lvl + 1);
eul[++elem] = nod;
nv[elem] = lvl;
}
}
}
int query (int x, int y){
int px , py , len;
px = first[x];
py = first[y];
if (px > py)
swap(px , py);
len = py - px + 1;
len = logg[len]; /// cea mai mare p2 <= len
if (nv[ rmq[len][px] ] < nv[ rmq[len][py - (1 << len) + 1] ])
return eul[ rmq[len][px] ];
else return eul[ rmq[len][py - (1 << len) + 1] ];
}
void adauga (int x , int y){
int lca , nod , poz , len;
lca = query(x , y); /// dc sa mai faci for cand poti face asta?
len = nivel[x] + nivel[y] - 2 * nivel[lca] + 1;
nod = x;
poz = 0;
while (nod != tt[lca]){
stare[nod].insert(make_pair(poz , len));
poz++;
if (poz == len)
poz = 0;
nod = tt[nod];
}
nod = y;
poz = len - 1;
while (nod != lca){
stare[nod].insert(make_pair(poz , len));
poz--;
if (poz == -1)
poz = len - 1;
nod = tt[nod];
}
}
void sterge (int x , int y){
int lca , nod , poz , len;
lca = query(x , y); /// dc sa mai faci for cand poti face asta?
len = nivel[x] + nivel[y] - 2 * nivel[lca] + 1;
nod = x;
poz = 0;
while (nod != tt[lca]){
stare[nod].erase(make_pair(poz , len));
poz++;
if (poz == len)
poz = 0;
nod = tt[nod];
}
nod = y;
poz = len - 1;
while (nod != lca){
stare[nod].erase(make_pair(poz , len));
poz--;
if (poz == -1)
poz = len - 1;
nod = tt[nod];
}
}
long long afla (int x , int y , int t1 , int t2){
int lca , nod , len , rest;
long long sol = 0;
lca = query(x , y); /// dc sa mai faci for cand poti face asta?
nod = x;
while (nod != tt[lca]){
for (set <pair <int,int> > :: iterator it = stare[nod].begin() ; it != stare[nod].end() ; it++){
len = it->second;
rest = it->first;
if (rest)
sol += (t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) + ((t1 - 1) % len >= rest);
else {
if (len != 1)
sol += (t2 / len) - ((t1 - 1) / len);
else sol += (t2 - t1 + 1);
}
}
nod = tt[nod];
}
nod = y;
while (nod != lca){
for (set <pair <int,int> > :: iterator it = stare[nod].begin() ; it != stare[nod].end() ; it++){
len = it->second;
rest = it->first;
if (rest)
sol += (t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) + ((t1 - 1) % len >= rest);
else {
if (len != 1)
sol += (t2 / len) - ((t1 - 1) / len);
else sol += (t2 - t1 + 1);
}
}
nod = tt[nod];
}
return sol;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , i , x , y , tip , k , q , powe , t1 , t2;
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 , 0);
for (i = 2 ; i <= elem ; i++)
logg[i] = 1 + logg[i / 2];
for (i = 1 ; i <= elem ; i++)
rmq[0][i] = i;
for (powe = 1 ; (1 << powe) <= elem ; powe++){
for (i = 1 ; i + (1 << powe) - 1 <= elem ; i++){
if (nv[ rmq[powe-1][i] ] < nv[ rmq[powe-1][i + (1 << (powe - 1) )] ])
rmq[powe][i] = rmq[powe-1][i];
else rmq[powe][i] = rmq[powe-1][i + (1 << (powe - 1) )];
}
}
fscanf (fin,"%d",&k);
for (i = 1 ; i <= k ; i++){
fscanf (fin,"%d%d",&x,&y);
adauga (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);
}
else if (tip == 2){
fscanf (fin,"%d%d",&x,&y);
sterge (x , y);
}
else {
fscanf (fin,"%d%d%d%d",&x,&y,&t1,&t2);
fprintf (fout,"%lld\n",afla (x , y , t1 , t2));
}
}
return 0;
}
Compilation message
traffickers.cpp: In function 'void dfs(int, int, int)':
traffickers.cpp:18:15: 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:145: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:147: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:171: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:174: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:179: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:181: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:183: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:187: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:191: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 |
9 ms |
7424 KB |
Output isn't correct |
| 2 |
Incorrect |
29 ms |
7936 KB |
Output isn't correct |
| 3 |
Incorrect |
16 ms |
7936 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1253 ms |
12508 KB |
Output isn't correct |
| 2 |
Incorrect |
1088 ms |
11896 KB |
Output isn't correct |
| 3 |
Incorrect |
1288 ms |
12664 KB |
Output isn't correct |
| 4 |
Incorrect |
1204 ms |
12408 KB |
Output isn't correct |
| 5 |
Incorrect |
1118 ms |
12280 KB |
Output isn't correct |
| 6 |
Incorrect |
1160 ms |
12408 KB |
Output isn't correct |
| 7 |
Incorrect |
1217 ms |
12344 KB |
Output isn't correct |
| 8 |
Incorrect |
1292 ms |
12408 KB |
Output isn't correct |
| 9 |
Incorrect |
3285 ms |
12920 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3572 ms |
37368 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3571 ms |
38520 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3584 ms |
38492 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3581 ms |
34040 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3573 ms |
25592 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3569 ms |
38988 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3572 ms |
39416 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3576 ms |
38908 KB |
Time limit exceeded |
