| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 212138 | 2020-03-22T10:27:25 Z | Ruxandra985 | Traffickers (RMI18_traffickers) | C++14 | 3500 ms | 39444 KB |
#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];
multiset <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++;
nod = tt[nod];
}
nod = y;
poz = len - 1;
while (nod != lca){
stare[nod].insert(make_pair(poz , len));
poz--;
nod = tt[nod];
}
}
void sterge (int x , int y){
int lca , nod , poz , len;
multiset <pair <int,int> > :: iterator it;
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]){
it = stare[nod].find(make_pair(poz , len));
stare[nod].erase(it);
poz++;
nod = tt[nod];
}
nod = y;
poz = len - 1;
while (nod != lca){
it = stare[nod].find(make_pair(poz , len));
stare[nod].erase(it);
poz--;
nod = tt[nod];
}
}
long long afla (int x , int y , int t1 , int t2){
int lca , nod , len , rest , val1 , val2;
long long sol = 0;
lca = query(x , y); /// dc sa mai faci for cand poti face asta?
nod = x;
while (nod != tt[lca]){
for (multiset <pair <int,int> > :: iterator it = stare[nod].begin() ; it != stare[nod].end() ; it++){
len = it->second;
rest = it->first;
sol += (t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) - ((t1 - 1) % len >= rest);
}
nod = tt[nod];
}
nod = y;
while (nod != lca){
for (multiset <pair <int,int> > :: iterator it = stare[nod].begin() ; it != stare[nod].end() ; it++){
len = it->second;
rest = it->first;
sol += (t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) - ((t1 - 1) % len >= rest);
val1 = (t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) - ((t1 - 1) % len >= rest);
val2 = 0;
for (int i = t1 ; i <= t2 ; i++){
if (i % len == rest)
val2++;
}
}
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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 7424 KB | Output is correct |
| 2 | Correct | 32 ms | 7936 KB | Output is correct |
| 3 | Correct | 17 ms | 7936 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1290 ms | 12192 KB | Output is correct |
| 2 | Correct | 1142 ms | 12076 KB | Output is correct |
| 3 | Correct | 1307 ms | 12408 KB | Output is correct |
| 4 | Correct | 1247 ms | 12536 KB | Output is correct |
| 5 | Correct | 1170 ms | 12408 KB | Output is correct |
| 6 | Correct | 1239 ms | 12316 KB | Output is correct |
| 7 | Correct | 1262 ms | 12208 KB | Output is correct |
| 8 | Correct | 1308 ms | 12280 KB | Output is correct |
| 9 | Correct | 3400 ms | 12504 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 3578 ms | 38520 KB | Time limit exceeded |
| 2 | Execution timed out | 3583 ms | 39288 KB | Time limit exceeded |
| 3 | Execution timed out | 3576 ms | 38912 KB | Time limit exceeded |
| 4 | Execution timed out | 3567 ms | 38220 KB | Time limit exceeded |
| 5 | Execution timed out | 3577 ms | 38264 KB | Time limit exceeded |
| 6 | Execution timed out | 3591 ms | 39444 KB | Time limit exceeded |
| 7 | Execution timed out | 3594 ms | 39160 KB | Time limit exceeded |
| 8 | Execution timed out | 3565 ms | 38812 KB | Time limit exceeded |