oj.uz

답안 #1102118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1102118 2024-10-17T13:40:52 Z epicci23 Inside information (BOI21_servers) C++17
50 / 100
 254 ms 60332 KB 
#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 4e4 + 5;
const int LOG = 20;
const int INF = 1e9;

int maxi[N][LOG],mini[N][LOG];
int lift[N][LOG],depth[N],ans[N],vis[N],sub[N],comp=0;
vector<array<int,2>> v[N],tag[N];

void dfs(int c){
  for(int i=1;i<LOG;i++) lift[c][i]=lift[lift[c][i-1]][i-1];
  
  for(int i=1;i<LOG;i++){
  	int u = maxi[c][i-1];
  	int u2 = maxi[lift[c][i-1]][i-1];
  	if(u==-1 || u2==-1) continue;
  	if(u>maxi[lift[c][i-1]][0]) continue;
    maxi[c][i]=u2;
  }

  for(int i=1;i<LOG;i++){
  	int u = mini[c][i-1];
  	int u2 = mini[lift[c][i-1]][i-1];
  	if(u==-1 || u2==-1) continue;
  	if(u<mini[lift[c][i-1]][0]) continue;
    mini[c][i]=u2;
  }

  for(auto E:v[c]){
   int x=E[0],y=E[1];
   if(x==lift[c][0]) continue;
   depth[x]=depth[c]+1;
   lift[x][0]=c;
   maxi[x][0]=mini[x][0]=y;
   dfs(x);
  }
}

inline int lca(int a,int b){
  if(depth[a]<depth[b]) swap(a,b);
  for(int i=0;i<LOG;i++) if((depth[a]-depth[b])>>i&1) a=lift[a][i];
  if(a==b) return a;
  for(int i=LOG-1;i>=0;i--){
  	if(lift[a][i]!=lift[b][i]){
  	  a=lift[a][i];
  	  b=lift[b][i];
  	}
  }
  return lift[a][0];
}

inline int yukari(int a,int u){
  int le = depth[a]-depth[u],lol = 0;
  for(int i=LOG-1;i>=0;i--){
    if(!(le>>i&1)) continue;
    if(maxi[a][i]==-1) return -1;
    if(lol>maxi[a][0]) return -1;
    lol=maxi[a][i];
    a=lift[a][i];
  }
  return lol;
}

inline int asagi(int a,int u){
  int le = depth[a]-depth[u],lol = INF;
  for(int i=LOG-1;i>=0;i--){
    if(!(le>>i&1)) continue;
    if(mini[a][i]==-1) return -1;
    if(lol<mini[a][0]) return -1;
    lol=mini[a][i];
    a=lift[a][i];
  }
  return lol;
}

inline int check(int a,int b){
  if(a==b) return 0;
  int c=lca(a,b);
  int hm = yukari(a,c);
  int hm2 = asagi(b,c);
  if(hm==-1 || hm2==-1 || hm>hm2) return -1;
  int xdd = hm;
  if(b!=c) xdd=max(xdd,maxi[b][0]);
  return xdd;
}

void precalc(int c,int p){
  sub[c]=1;
  comp++;
  for(auto E:v[c]){
    int x = E[0];
    if(x==p || vis[x]) continue;
    precalc(x,c);
    sub[c]+=sub[x];
  }
}

int find_centroid(int c,int p){
  for(auto E:v[c]){
    int x = E[0];
    if(x==p || vis[x]) continue;
    if(sub[x]>comp/2) return find_centroid(x,c);
  }
  return c;
}

int fw[N];

inline void Upd(int c,int u){
  for(;c<N;c+=c&-c) fw[c]+=u;    
}

inline int Query(int c,int res=0){
  for(;c;c-=c&-c) res+=fw[c];
  return res;
}

void Add(int c,int p,int last,int val){
  Upd(last,val);
  for(auto E:v[c]){
    int x=E[0],u=E[1];
    if(vis[x] || x==p || last>u) continue;
    Add(x,c,u,val);
  }
}

void Get(int c,int p,int bruh,int azal){
  for(auto x:tag[c]){
    if(bruh>x[1]) continue;
    ans[x[1]]+=Query(x[0])+1;
  }
  for(auto E:v[c]){
    int x=E[0],u=E[1];
    if(vis[x] || x==p || azal<u) continue;
    Get(x,c,bruh,u);
  }
}

void centroid(int c,int p){
  comp=0;precalc(c,p);
  c=find_centroid(c,p);
  sort(all(v[c]),[&](array<int,2> a,array<int,2> b){
    return a[1]>b[1];
  });
  for(auto E:v[c]){
    int x = E[0], u = E[1];
    if(x==p || vis[x]) continue;
    Get(x,c,u,u);
    Add(x,c,u,1);
  }
  for(auto x:tag[c]) ans[x[1]]+=Query(x[0]);
  for(auto E:v[c]){
    int x = E[0], u = E[1];
    if(x==p || vis[x]) continue;
    Add(x,c,u,-1);
  }
  vis[c]=1;
  for(auto E:v[c]){
    int x = E[0], u = E[1];
    if(x==p || vis[x]) continue;
    centroid(x,c);
  }
}

void _(){
  memset(maxi,-1,sizeof(maxi));
  memset(mini,-1,sizeof(mini));

  int n,q;
  cin >> n >> q;
  
  vector<array<int,4>> cevapla;
  int cp=0,ed=0;

  for(int i=1;i<n+q;i++){
    char op;
    cin >> op;
    if(op=='S'){
     int a,b;
     cin >> a >> b;
     ++ed;
     v[a].push_back({b,ed});
     v[b].push_back({a,ed});
    }
    else if(op=='Q'){
      int a,b;
      cin >> a >> b;
      ++cp;
      cevapla.push_back({b,a,ed,cp});
    }
    else{
      int a;
      cin >> a;
      ++cp;
      tag[a].push_back({ed,cp});
    }
  }
  dfs(1);
  for(auto x:cevapla){
    int res = check(x[0],x[1]);
    if(res==-1 || res>x[2]) ans[x[3]]=-2;
    else ans[x[3]]=-1; 
  }
  centroid(1,1);
  for(int i=1;i<=cp;i++){
    if(ans[i]==-2) cout << "no\n";
    else if(ans[i]==-1) cout << "yes\n";
    else cout << ans[i] + 1 << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

Compilation message

servers.cpp: In function 'void centroid(int, int)':
servers.cpp:164:19: warning: unused variable 'u' [-Wunused-variable]
  164 |     int x = E[0], u = E[1];
      |                   ^

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 31632 KB Output is correct
2 Correct 49 ms 32212 KB Output is correct
3 Correct 47 ms 32164 KB Output is correct
4 Correct 55 ms 32252 KB Output is correct
5 Correct 57 ms 32440 KB Output is correct
6 Correct 46 ms 32240 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 31632 KB Output is correct
2 Correct 49 ms 32212 KB Output is correct
3 Correct 47 ms 32164 KB Output is correct
4 Correct 55 ms 32252 KB Output is correct
5 Correct 57 ms 32440 KB Output is correct
6 Correct 46 ms 32240 KB Output is correct
7 Incorrect 43 ms 31640 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 31688 KB Output is correct
2 Correct 134 ms 47536 KB Output is correct
3 Correct 149 ms 49104 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 31688 KB Output is correct
2 Correct 134 ms 47536 KB Output is correct
3 Correct 149 ms 49104 KB Output is correct
4 Incorrect 43 ms 31680 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 31764 KB Output is correct
2 Correct 220 ms 58040 KB Output is correct
3 Correct 210 ms 58040 KB Output is correct
4 Correct 214 ms 58040 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 31764 KB Output is correct
2 Correct 220 ms 58040 KB Output is correct
3 Correct 210 ms 58040 KB Output is correct
4 Correct 214 ms 58040 KB Output is correct
5 Incorrect 38 ms 31516 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 31820 KB Output is correct
2 Correct 139 ms 47196 KB Output is correct
3 Correct 149 ms 47800 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 31820 KB Output is correct
2 Correct 139 ms 47196 KB Output is correct
3 Correct 149 ms 47800 KB Output is correct
4 Incorrect 44 ms 32448 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 31844 KB Output is correct
2 Correct 190 ms 57868 KB Output is correct
3 Correct 202 ms 60332 KB Output is correct
4 Correct 199 ms 58040 KB Output is correct
5 Correct 43 ms 31624 KB Output is correct
6 Correct 122 ms 48240 KB Output is correct
7 Correct 128 ms 47800 KB Output is correct
8 Correct 193 ms 48700 KB Output is correct
9 Correct 171 ms 48824 KB Output is correct
10 Correct 224 ms 53768 KB Output is correct
11 Correct 254 ms 52920 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 31844 KB Output is correct
2 Correct 190 ms 57868 KB Output is correct
3 Correct 202 ms 60332 KB Output is correct
4 Correct 199 ms 58040 KB Output is correct
5 Correct 43 ms 31624 KB Output is correct
6 Correct 122 ms 48240 KB Output is correct
7 Correct 128 ms 47800 KB Output is correct
8 Correct 193 ms 48700 KB Output is correct
9 Correct 171 ms 48824 KB Output is correct
10 Correct 224 ms 53768 KB Output is correct
11 Correct 254 ms 52920 KB Output is correct
12 Incorrect 42 ms 31600 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 31680 KB Output is correct
2 Correct 56 ms 32984 KB Output is correct
3 Correct 47 ms 32232 KB Output is correct
4 Correct 58 ms 32368 KB Output is correct
5 Correct 56 ms 32440 KB Output is correct
6 Correct 57 ms 32232 KB Output is correct
7 Correct 44 ms 32456 KB Output is correct
8 Correct 133 ms 49844 KB Output is correct
9 Correct 137 ms 47564 KB Output is correct
10 Correct 44 ms 31652 KB Output is correct
11 Correct 191 ms 58040 KB Output is correct
12 Correct 195 ms 60088 KB Output is correct
13 Correct 188 ms 59452 KB Output is correct
14 Correct 50 ms 32412 KB Output is correct
15 Correct 112 ms 47288 KB Output is correct
16 Correct 125 ms 49336 KB Output is correct
17 Correct 190 ms 48444 KB Output is correct
18 Correct 185 ms 49848 KB Output is correct
19 Correct 241 ms 53736 KB Output is correct
20 Correct 248 ms 52920 KB Output is correct
21 Correct 147 ms 48772 KB Output is correct
22 Correct 137 ms 49360 KB Output is correct
23 Correct 152 ms 50360 KB Output is correct
24 Correct 149 ms 48100 KB Output is correct
25 Correct 228 ms 53352 KB Output is correct
26 Correct 180 ms 48824 KB Output is correct
27 Correct 178 ms 49000 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 31680 KB Output is correct
2 Correct 56 ms 32984 KB Output is correct
3 Correct 47 ms 32232 KB Output is correct
4 Correct 58 ms 32368 KB Output is correct
5 Correct 56 ms 32440 KB Output is correct
6 Correct 57 ms 32232 KB Output is correct
7 Correct 44 ms 32456 KB Output is correct
8 Correct 133 ms 49844 KB Output is correct
9 Correct 137 ms 47564 KB Output is correct
10 Correct 44 ms 31652 KB Output is correct
11 Correct 191 ms 58040 KB Output is correct
12 Correct 195 ms 60088 KB Output is correct
13 Correct 188 ms 59452 KB Output is correct
14 Correct 50 ms 32412 KB Output is correct
15 Correct 112 ms 47288 KB Output is correct
16 Correct 125 ms 49336 KB Output is correct
17 Correct 190 ms 48444 KB Output is correct
18 Correct 185 ms 49848 KB Output is correct
19 Correct 241 ms 53736 KB Output is correct
20 Correct 248 ms 52920 KB Output is correct
21 Correct 147 ms 48772 KB Output is correct
22 Correct 137 ms 49360 KB Output is correct
23 Correct 152 ms 50360 KB Output is correct
24 Correct 149 ms 48100 KB Output is correct
25 Correct 228 ms 53352 KB Output is correct
26 Correct 180 ms 48824 KB Output is correct
27 Correct 178 ms 49000 KB Output is correct
28 Incorrect 43 ms 32192 KB Extra information in the output file
29 Halted 0 ms 0 KB -