Submission #50911

#TimeUsernameProblemLanguageResultExecution timeMemory
50911NicksechkoBirthday gift (IZhO18_treearray)C++14
100 / 100
3233 ms300008 KiB
#ifndef LOCAL #pragma GCC optimize "-O3" #endif #include <bits/stdc++.h> typedef long long ll; typedef long long llong; typedef long double ld; typedef unsigned long long ull; using namespace std; /* ll pw(ll a, ll b) { ll ans = 1; while (b) { while (!(b & 1)) b >>= 1, a = (a * a) % MOD; ans = (ans * a) % MOD, --b; } return ans; } */ const int LOG = 20; const int MAXN = 220000; int tin[MAXN]; int tout[MAXN]; int up[LOG][MAXN]; vector<int> eds[MAXN]; set<int> g1[MAXN]; set<int> g2[MAXN]; int tm1; int a[MAXN]; int n, m, q; void dfs1(int v, int p) { tin[v] = tm1++; for (int u: eds[v]) { if (u == p) continue; up[0][u] = v; dfs1(u, v); } tout[v] = tm1; } int is_p(int a, int b) { return tin[a] <= tin[b] && tin[b] < tout[a]; } int lca(int a, int b) { if (is_p(a, b)) return a; for (int i = LOG - 1; i >= 0; --i) { if (!is_p(up[i][a], b)) a = up[i][a]; } return up[0][a]; } int main() { scanf("%d%d%d", &n, &m, &q); for (int i = 0; i < n - 1; ++i) { int a, b; scanf("%d%d", &a, &b); --a, --b; eds[a].push_back(b); eds[b].push_back(a); } for (int i = 0; i < m; ++i) { scanf("%d", a + i); --a[i]; } dfs1(0, -1); for (int i = 1; i < LOG; ++i) { for (int j = 0; j < n; ++j) up[i][j] = up[i - 1][up[i - 1][j]]; } for (int i = 0; i < m; ++i) { g1[a[i]].insert(i); if (i < m - 1) g2[lca(a[i], a[i + 1])].insert(i); } for (int i = 0; i < q; ++i) { int t; scanf("%d", &t); if (t == 1) { int ps, v; scanf("%d%d", &ps, &v); --ps, --v; g1[a[ps]].erase(ps); if (ps < m - 1) g2[lca(a[ps], a[ps + 1])].erase(ps); if (ps > 0) g2[lca(a[ps], a[ps - 1])].erase(ps - 1); a[ps] = v; g1[a[ps]].insert(ps); if (ps < m - 1) g2[lca(a[ps], a[ps + 1])].insert(ps); if (ps > 0) g2[lca(a[ps], a[ps - 1])].insert(ps - 1); } else { int l, r, v; scanf("%d%d%d", &l, &r, &v); --l, --r, --v; auto it1 = g1[v].lower_bound(l); if (it1 != g1[v].end() && *it1 <= r) { printf("%d %d\n", *it1 + 1, *it1 + 1); } else { auto it2 = g2[v].lower_bound(l); if (it2 != g2[v].end() && *it2 < r) { printf("%d %d\n", *it2 + 1, *it2 + 1 + 1); } else { printf("-1 -1\n"); } } } } return 0; }

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~
treearray.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
treearray.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &ps, &v);
    ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d", &l, &r, &v);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...