結果
問題 | No.1197 モンスターショー |
ユーザー |
![]() |
提出日時 | 2020-08-22 16:12:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,212 bytes |
コンパイル時間 | 3,291 ms |
コンパイル使用メモリ | 209,816 KB |
最終ジャッジ日時 | 2025-01-13 10:05:21 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 TLE * 9 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:110:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 110 | scanf("%d",&pos[i]); | ~~~~~^~~~~~~~~~~~~~ main.cpp:118:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 118 | scanf("%d %d",&a,&b); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:149:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 149 | scanf("%d",&t); | ~~~~~^~~~~~~~~ main.cpp:153:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 153 | scanf("%d %d",&p,&d); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:169:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 169 | scanf("%d",&e); | ~~~~~^~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 998244353 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000005 vector<pair<int,int>> order; vector<int> L; int N,K,Q; vector<int> dis; vector<long long> calc; vector<int> cnt; vector<int> C; template <typename T> struct sparse_table{ const T init_value = make_pair(1000000001,1000001); vector<T> v; int n; int sz; sparse_table(vector<T> &x){ sz = x.size(); for(int i=0;true;i++){ if((1<<i)>sz){ n = i; break; } } v.resize(sz*n,init_value); for(int i=0;i<sz;i++){ v[i] = x[i]; } for(int i=1;i<n;i++){ for(int j=0;j<sz+1-(1<<i);j++){ int temp = j+(1<<(i-1)); v[i*sz+j] = func(v[(i-1)*sz+j],v[(i-1)*sz+temp]); } } } T query(int l,int r){ int x = 31-__builtin_clz(r-l); return func(v[sz*x+l],v[sz*x+r-(1<<x)]); } T func(T a,T b){ return min(a,b); } }; void dfs(vector<vector<int>> &E,int now,int p){ cnt[now] = C[now]; for(int i=0;i<E[now].size();i++){ dfs(E,E[now][i],now); cnt[now] += cnt[E[now][i]]; } } void dfs2(vector<vector<int>> &E,int now,int p){ if(p==-1){ calc[now] = 0; for(int i=0;i<N;i++){ calc[now] += (long long)dis[i] * C[i]; } } else{ calc[now] = calc[p]; calc[now] -= cnt[now]; calc[now] += K-cnt[now]; } for(int i=0;i<E[now].size();i++){ dfs2(E,E[now][i],now); } } void Erasedfs(vector<vector<int>> &E,int now,int p,int d=0){ dis[now] =d; L[now] = order.size(); order.emplace_back(d,now); vector<int> t; for(int i=0;i<E[now].size();i++){ if(E[now][i]==p)continue; t.push_back(E[now][i]); Erasedfs(E,E[now][i],now,d+1); order.emplace_back(d,now); } E[now] = t; } int get_distance(sparse_table<pair<int,int>> &S,int u,int v){ if(u==v)return 0; int l = min(L[u],L[v]); int r = max(L[u],L[v]); int x = S.query(l,r+1).second; return dis[u]+dis[v]-2*dis[x]; } int main(){ cin>>N>>K>>Q; C.resize(N,0); vector<int> pos(K); for(int i=0;i<K;i++){ scanf("%d",&pos[i]); pos[i]--; C[pos[i]]++; } vector<vector<int>> E(N); for(int i=0;i<N-1;i++){ int a,b; scanf("%d %d",&a,&b); a--;b--; E[a].push_back(b); E[b].push_back(a); } dis.resize(N); L.resize(N); Erasedfs(E,0,-1); sparse_table<pair<int,int>> S(order); calc.resize(N); cnt.resize(N); dfs(E,0,-1); dfs2(E,0,-1); vector<pair<int,int>> Movement; for(int i=0;i<Q;i++){ if(Movement.size()>200){ for(int j=0;j<Movement.size();j++){ C[pos[Movement[j].first]]--; pos[Movement[j].first] = Movement[j].second; C[pos[Movement[j].first]]++; } Movement.resize(0); dfs(E,0,-1); dfs2(E,0,-1); } int t; scanf("%d",&t); if(t==1){ int p,d; scanf("%d %d",&p,&d); p--;d--; bool f = false; for(int j=0;j<Movement.size();j++){ if(Movement[j].first==p){ Movement[j].second = d; f=true; break; } } if(!f)Movement.emplace_back(p,d); } else{ int e; scanf("%d",&e); e--; long long ans = calc[e]; for(int j=0;j<Movement.size();j++){ ans -= get_distance(S,e,pos[Movement[j].first]); ans += get_distance(S,e,Movement[j].second); } printf("%lld\n",ans); } } return 0; }