제출 #865679

#제출 시각아이디문제언어결과실행 시간메모리
865679vjudge1Birthday gift (IZhO18_treearray)C++17
0 / 100
3 ms14940 KiB
#include <bits/stdc++.h> #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) #define optimus_prime ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define fxd(x) fixed << setprecision(x) #define all(a) (a.begin() , a.end()) #define popcount(x) __builtin_popcount(x) #define lwb lower_bound #define upb upper_bound #define dl double long #define ll long long #define pb push_back #define sz() size() #define F first #define S second using namespace std; const ll N = 1e5+9; const ll L = 30; ll n , m , q , a[N] , tin[N] , tout[N] , timer , h[N] , up[N][L]; vector <int> g[N]; set <int> st[N] , st1[N]; void calc(ll cur , ll p , ll len=1){ h[cur]=len; tin[cur]=++timer; up[cur][0]=p; for (int i = 1 ; i <= L ; i++)up[cur][i]=up[up[cur][i-1]][i-1]; for (auto to : g[cur]){ if (to!=p)calc(to , cur , len+1); } tout[cur]=timer; } bool upper(ll a , ll b){ if (tin[a]<=tin[b]&&tout[b]<=tout[a])return 1; return 0; } ll lca(ll a , ll b){ if (upper(a , b))return a; if (upper(b , a))return b; for (int i = L ; i >= 0 ; i--){ if (!upper(up[a][i] , b))a=up[a][i]; } return up[a][0]; } void solve(){ cin >> n >> m >> q; for (int i = 1 ; i < n ; i++){ ll u , v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } calc(1 , 1); for (int i = 1 ; i <= m ; i++){ cin >> a[i]; st[a[i]].insert(i); if (i>1)st1[lca(a[i-1] , a[i])].insert(i-1); } while (q--){ ll tp; cin >> tp; if (tp==1){ ll pos , v; cin >> pos >> v; if (pos<m)st1[lca(a[pos] , a[pos+1])].erase(pos); if (pos>1)st1[lca(a[pos-1] , a[pos])].erase(pos-1); st[a[pos]].erase(pos); a[pos]=v; st[a[pos]].insert(pos); if (pos<m)st1[lca(a[pos] , a[pos+1])].insert(pos); if (pos>1)st1[lca(a[pos-1] , a[pos])].insert(pos-1); } else { ll l , r , v; cin >> l >> r >> v; if (st[v].lwb(l)!=st[v].end() && (*st[v].lwb(l))<=r){ ll x=*(st[v].lwb(l)); cout << x << " " << x << "\n"; } else if (st1[v].lwb(l)!=st1[v].end() && (*st1[v].lwb(l))<r){ ll x=*(st1[v].lwb(l)); cout << x << " " << x+1 << "\n"; } else cout << "-1 -1\n"; } } } signed main() { optimus_prime; solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

treearray.cpp: In function 'void calc(long long int, long long int, long long int)':
treearray.cpp:30:42: warning: iteration 29 invokes undefined behavior [-Waggressive-loop-optimizations]
   30 |  for (int i = 1 ; i <= L ; i++)up[cur][i]=up[up[cur][i-1]][i-1];
      |                                ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:30:21: note: within this loop
   30 |  for (int i = 1 ; i <= L ; i++)up[cur][i]=up[up[cur][i-1]][i-1];
      |                   ~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...