oj.uz

Submission #818923

# Submission time Handle Problem Language Result Execution time Memory
818923 2023-08-10T07:19:38 Z winter0101 Inside information (BOI21_servers) C++14
100 / 100
 420 ms 91168 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const int maxn=1e5+2e4+9;
struct query{
char quest;
int x,y;
}qr[maxn*2];
vector<pii>a[maxn];
int n,k;
int sub[maxn];
bool use[maxn];
void dfs(int u,int par){
sub[u]=1;
for (auto v:a[u]){
    if (v.fi==par||use[v.fi])continue;
    dfs(v.fi,u);
    sub[u]+=sub[v.fi];
}
}
int cen(int u,int par,int mx){
for(auto v:a[u]){
    if (use[v.fi]||v.fi==par)continue;
    if (sub[v.fi]*2>mx)return cen(v.fi,u,mx);
}
return u;
}
int dep[maxn],p[maxn];
pii mx[maxn][18],mn[maxn][18];
vector<int>ask[maxn];
int ans[maxn*2];
struct vertice{
int val,u,type;
bool operator < (const vertice &p1){
if (val==p1.val)return type<p1.type;
return val>p1.val;
}
};
vector<vertice>len[maxn];
void dfsmax(int u,int par,int s,int e,int root){
mx[u][dep[root]]={s,e};
if (par)len[root].pb({s,u,1});
for (auto v:a[u]){
    if (v.fi==par||use[v.fi])continue;
    int news=s,newe=e;
    if (e<=v.se)continue;
    if (s==n+k)news=v.se;
    newe=v.se;
    dfsmax(v.fi,u,news,newe,root);
}
}
void dfsmin(int u,int par,int s,int e,int root){
mn[u][dep[root]]={s,e};
if (par){
len[root].pb({s,u,2});
}
for (auto v:a[u]){
    if (v.fi==par||use[v.fi])continue;
    int news=s,newe=e;
    if (e>=v.se)continue;
    newe=v.se;
    if (s==0)news=v.se;
    dfsmin(v.fi,u,news,newe,root);
}
}
struct BIT{
vector<int>bit;
int m;
void resz(int _n){
m=_n;
bit.resize(m+1);
}
void add(int pos,int val){
//cerr<<"ADD "<<pos<<'\n';
for(;pos<=m;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
int get(int pos){
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
int get(int l,int r){
if (l>r)return 0;
return get(r)-get(l-1);
}
}bit;
void decompose(int u,int c){
dfs(u,0);
int newcen=cen(u,0,sub[u]);
//cerr<<newcen<<'\n';
if (c)dep[newcen]=dep[c]+1,p[newcen]=c;
dfsmax(newcen,0,n+k,n+k,newcen);
dfsmin(newcen,0,0,0,newcen);
sort(all(len[newcen]));
for (auto v:len[newcen]){
    if (v.type==2){
       //cerr<<v.u<<" "<<mx[v.u][dep[newcen]].se<<'\n';
       bit.add(mn[v.u][dep[newcen]].se,1);
    }
    else {
       for (auto v1:ask[v.u]){
        if (v.val<=v1)ans[v1]+=bit.get(v1)+1;
       }
    }
}
for (auto v:ask[newcen]){
    ans[v]+=1+bit.get(v);
}
for (auto v:len[newcen])if (v.type==2)bit.add(mn[v.u][dep[newcen]].se,-1);
use[newcen]=1;
for (auto v:a[newcen]){
    if (use[v.fi])continue;
    decompose(v.fi,newcen);
}
}
int lca(int u,int v){
if (dep[u]<dep[v])swap(u,v);
int k1=dep[u]-dep[v];
for1(i,1,k1)u=p[u];
if (u==v)return u;
while (true){
    if (u==v)return u;
    u=p[u];
    v=p[v];
}
}
void init(){
cin>>n>>k;
for1(i,1,n+k-1){
cin>>qr[i].quest;
if (qr[i].quest=='C')cin>>qr[i].x;
else cin>>qr[i].x>>qr[i].y;
if (qr[i].quest=='S'){
    a[qr[i].x].pb({qr[i].y,i});
    a[qr[i].y].pb({qr[i].x,i});
}
if (qr[i].quest=='C'){
    ask[qr[i].x].pb(i);
}
}
bit.resz(n+k);
}
bool dosmth(int u,int v,int t){
//edg tang dan tu v
int m=lca(u,v);
//cerr<<m<<'\n';
if (u==v)return 1;
if (u==m){
    if (mx[v][dep[m]].fi<=t&&mx[v][dep[m]].fi>0)return 1;
    return 0;
}
if (v==m){
    if (mn[u][dep[m]].se<=t&&mn[u][dep[m]].se>0)return 1;
    return 0;
}
if (mn[u][dep[m]].se<=0||mx[v][dep[m]].fi<=0)return 0;
if (mn[u][dep[m]].se>t)return 0;
if (mn[u][dep[m]].fi>mx[v][dep[m]].fi)return 1;
return 0;
}
void solve(){
for1(i,1,n+k-1){
if (qr[i].quest=='S')continue;
if (qr[i].quest=='Q'){
     if (dosmth(qr[i].x,qr[i].y,i))cout<<"yes"<<'\n';
     else cout<<"no"<<'\n';
}
else {
    cout<<ans[i]<<'\n';
}
}
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    init();
    decompose(1,0);
    solve();
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11852 KB Output is correct
2 Correct 31 ms 13924 KB Output is correct
3 Correct 33 ms 13996 KB Output is correct
4 Correct 32 ms 14028 KB Output is correct
5 Correct 36 ms 14296 KB Output is correct
6 Correct 38 ms 14064 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11852 KB Output is correct
2 Correct 31 ms 13924 KB Output is correct
3 Correct 33 ms 13996 KB Output is correct
4 Correct 32 ms 14028 KB Output is correct
5 Correct 36 ms 14296 KB Output is correct
6 Correct 38 ms 14064 KB Output is correct
7 Correct 35 ms 12188 KB Output is correct
8 Correct 34 ms 14652 KB Output is correct
9 Correct 29 ms 14600 KB Output is correct
10 Correct 34 ms 14656 KB Output is correct
11 Correct 34 ms 14788 KB Output is correct
12 Correct 30 ms 14560 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11972 KB Output is correct
2 Correct 183 ms 59424 KB Output is correct
3 Correct 176 ms 59372 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11972 KB Output is correct
2 Correct 183 ms 59424 KB Output is correct
3 Correct 176 ms 59372 KB Output is correct
4 Correct 24 ms 12272 KB Output is correct
5 Correct 188 ms 60340 KB Output is correct
6 Correct 168 ms 59868 KB Output is correct
7 Correct 175 ms 60048 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11972 KB Output is correct
2 Correct 217 ms 70108 KB Output is correct
3 Correct 219 ms 70176 KB Output is correct
4 Correct 248 ms 89436 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11972 KB Output is correct
2 Correct 217 ms 70108 KB Output is correct
3 Correct 219 ms 70176 KB Output is correct
4 Correct 248 ms 89436 KB Output is correct
5 Correct 28 ms 12140 KB Output is correct
6 Correct 251 ms 72052 KB Output is correct
7 Correct 268 ms 91096 KB Output is correct
8 Correct 259 ms 72464 KB Output is correct
9 Correct 235 ms 72504 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11960 KB Output is correct
2 Correct 253 ms 78496 KB Output is correct
3 Correct 185 ms 63260 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11960 KB Output is correct
2 Correct 253 ms 78496 KB Output is correct
3 Correct 185 ms 63260 KB Output is correct
4 Correct 24 ms 12132 KB Output is correct
5 Correct 248 ms 80504 KB Output is correct
6 Correct 167 ms 64588 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11852 KB Output is correct
2 Correct 180 ms 70104 KB Output is correct
3 Correct 206 ms 70104 KB Output is correct
4 Correct 220 ms 89484 KB Output is correct
5 Correct 22 ms 11868 KB Output is correct
6 Correct 203 ms 78504 KB Output is correct
7 Correct 178 ms 63336 KB Output is correct
8 Correct 202 ms 63508 KB Output is correct
9 Correct 213 ms 63396 KB Output is correct
10 Correct 288 ms 82864 KB Output is correct
11 Correct 282 ms 82260 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11852 KB Output is correct
2 Correct 180 ms 70104 KB Output is correct
3 Correct 206 ms 70104 KB Output is correct
4 Correct 220 ms 89484 KB Output is correct
5 Correct 22 ms 11868 KB Output is correct
6 Correct 203 ms 78504 KB Output is correct
7 Correct 178 ms 63336 KB Output is correct
8 Correct 202 ms 63508 KB Output is correct
9 Correct 213 ms 63396 KB Output is correct
10 Correct 288 ms 82864 KB Output is correct
11 Correct 282 ms 82260 KB Output is correct
12 Correct 27 ms 12132 KB Output is correct
13 Correct 227 ms 72108 KB Output is correct
14 Correct 236 ms 91168 KB Output is correct
15 Correct 230 ms 72512 KB Output is correct
16 Correct 216 ms 72548 KB Output is correct
17 Correct 23 ms 12244 KB Output is correct
18 Correct 230 ms 80548 KB Output is correct
19 Correct 192 ms 64672 KB Output is correct
20 Correct 213 ms 65400 KB Output is correct
21 Correct 224 ms 65496 KB Output is correct
22 Correct 323 ms 83996 KB Output is correct
23 Correct 391 ms 83364 KB Output is correct
24 Correct 368 ms 83116 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11856 KB Output is correct
2 Correct 31 ms 13996 KB Output is correct
3 Correct 28 ms 14040 KB Output is correct
4 Correct 32 ms 14028 KB Output is correct
5 Correct 36 ms 14284 KB Output is correct
6 Correct 34 ms 14028 KB Output is correct
7 Correct 22 ms 12016 KB Output is correct
8 Correct 165 ms 59352 KB Output is correct
9 Correct 171 ms 59372 KB Output is correct
10 Correct 25 ms 12048 KB Output is correct
11 Correct 186 ms 70176 KB Output is correct
12 Correct 180 ms 70108 KB Output is correct
13 Correct 227 ms 89456 KB Output is correct
14 Correct 27 ms 11944 KB Output is correct
15 Correct 199 ms 78432 KB Output is correct
16 Correct 154 ms 63248 KB Output is correct
17 Correct 216 ms 63616 KB Output is correct
18 Correct 222 ms 63432 KB Output is correct
19 Correct 265 ms 82852 KB Output is correct
20 Correct 271 ms 82268 KB Output is correct
21 Correct 187 ms 61324 KB Output is correct
22 Correct 220 ms 61728 KB Output is correct
23 Correct 188 ms 62688 KB Output is correct
24 Correct 219 ms 62788 KB Output is correct
25 Correct 220 ms 65332 KB Output is correct
26 Correct 247 ms 70072 KB Output is correct
27 Correct 243 ms 71416 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11856 KB Output is correct
2 Correct 31 ms 13996 KB Output is correct
3 Correct 28 ms 14040 KB Output is correct
4 Correct 32 ms 14028 KB Output is correct
5 Correct 36 ms 14284 KB Output is correct
6 Correct 34 ms 14028 KB Output is correct
7 Correct 22 ms 12016 KB Output is correct
8 Correct 165 ms 59352 KB Output is correct
9 Correct 171 ms 59372 KB Output is correct
10 Correct 25 ms 12048 KB Output is correct
11 Correct 186 ms 70176 KB Output is correct
12 Correct 180 ms 70108 KB Output is correct
13 Correct 227 ms 89456 KB Output is correct
14 Correct 27 ms 11944 KB Output is correct
15 Correct 199 ms 78432 KB Output is correct
16 Correct 154 ms 63248 KB Output is correct
17 Correct 216 ms 63616 KB Output is correct
18 Correct 222 ms 63432 KB Output is correct
19 Correct 265 ms 82852 KB Output is correct
20 Correct 271 ms 82268 KB Output is correct
21 Correct 187 ms 61324 KB Output is correct
22 Correct 220 ms 61728 KB Output is correct
23 Correct 188 ms 62688 KB Output is correct
24 Correct 219 ms 62788 KB Output is correct
25 Correct 220 ms 65332 KB Output is correct
26 Correct 247 ms 70072 KB Output is correct
27 Correct 243 ms 71416 KB Output is correct
28 Correct 23 ms 12176 KB Output is correct
29 Correct 33 ms 14592 KB Output is correct
30 Correct 37 ms 14576 KB Output is correct
31 Correct 34 ms 14616 KB Output is correct
32 Correct 36 ms 14824 KB Output is correct
33 Correct 34 ms 14616 KB Output is correct
34 Correct 23 ms 12244 KB Output is correct
35 Correct 176 ms 60308 KB Output is correct
36 Correct 163 ms 59932 KB Output is correct
37 Correct 151 ms 60056 KB Output is correct
38 Correct 26 ms 12112 KB Output is correct
39 Correct 234 ms 72072 KB Output is correct
40 Correct 249 ms 91156 KB Output is correct
41 Correct 222 ms 72524 KB Output is correct
42 Correct 227 ms 72540 KB Output is correct
43 Correct 23 ms 12236 KB Output is correct
44 Correct 226 ms 80600 KB Output is correct
45 Correct 162 ms 64604 KB Output is correct
46 Correct 216 ms 65356 KB Output is correct
47 Correct 221 ms 65492 KB Output is correct
48 Correct 305 ms 84088 KB Output is correct
49 Correct 420 ms 83320 KB Output is correct
50 Correct 372 ms 83056 KB Output is correct
51 Correct 177 ms 62532 KB Output is correct
52 Correct 154 ms 60804 KB Output is correct
53 Correct 151 ms 60520 KB Output is correct
54 Correct 172 ms 61112 KB Output is correct
55 Correct 145 ms 62300 KB Output is correct
56 Correct 167 ms 63568 KB Output is correct
57 Correct 214 ms 66316 KB Output is correct
58 Correct 271 ms 70464 KB Output is correct
59 Correct 251 ms 71996 KB Output is correct