제출 #523398

#제출 시각아이디문제언어결과실행 시간메모리
523398KalashnikovBirthday gift (IZhO18_treearray)C++17
100 / 100
950 ms83536 KiB
#include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) #define all(a) a.begin() , a.end() #define F first #define S second using namespace std; using ll = long long; const int N = 2e5+5 , inf = 2e9 + 7; const ll INF = 1e18 , mod = 1e9+7 , P = 6547; int a[N]; vector<int> g[N]; int tin[N] , tout[N] , timer; int up[N][20]; void dfs(int v = 1, int p = 0) { up[v][0] = p; for(int i = 1; i < 20; i ++) { up[v][i] = up[up[v][i-1]][i-1]; } tin[v] = ++timer; for(auto to: g[v]) { if(to != p) { dfs(to , v); } } tout[v] = ++timer; } bool upper(int a , int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; } int lca(int a , int b) { if(upper(a , b)) return a; if(upper(b , a)) return b; for(int i = 19; i >= 0; i --) { if(up[a][i] && !upper(up[a][i] , b)) { a = up[a][i]; } } return up[a][0]; } set<int> st1[N]; set<int> st2[N]; void solve(int tc) { int n , m , q; cin >> n >> m >> q; for(int i = 1; i < n; i ++) { int a , b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } dfs(); for(int i = 1; i <= m; i ++) { cin >> a[i]; st1[a[i]].insert(i); } for(int i = 1; i < m; i ++) { st2[lca(a[i] , a[i+1])].insert(i); } while(q --) { int t; cin >> t; if(t == 2) { int l , r , v; cin >> l >> r >> v; int fnd = 0; auto it = st1[v].lower_bound(l); if(it != st1[v].end() && *it <= r) { fnd = 1; cout << *it << ' ' << *it << '\n'; } if(fnd == 0) { auto it = st2[v].lower_bound(l); if(it != st2[v].end() && *it < r) { fnd = 1; cout << *it << ' ' << *it+1 << '\n'; } else { cout << "-1 -1\n"; } } } else { int pos , val; cin >> pos >> val; st1[a[pos]].erase(pos); if(pos != 1) st2[lca(a[pos-1] , a[pos])].erase(pos-1); if(pos != m) st2[lca(a[pos+1] , a[pos])].erase(pos); a[pos] = val; st1[a[pos]].insert(pos); if(pos != 1) st2[lca(a[pos-1] , a[pos])].insert(pos-1); if(pos != m) st2[lca(a[pos+1] , a[pos])].insert(pos); } } } /* */ main() { ios; int tt = 1 , tc = 0; // cin >> tt; while(tt --) { solve(++tc); } return 0; }

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

treearray.cpp:117:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  117 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...