Submission #999912

#TimeUsernameProblemLanguageResultExecution timeMemory
999912vjudge1Construction of Highway (JOI18_construction)C++17
16 / 100
2024 ms9116 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define all(v) v.begin(), v.end() #define oo 1e9 const int MAX = 1e5 + 5; int n; int tree[MAX]; void init(){ for(int i = 0; i < MAX; i++) tree[i] = 0; } void update(int pos, int val){ for(int i = pos; i < MAX; i += (i & -i)) tree[i] += val; } int ask(int l, int r){ if(l != 1) return ask(1, r) - ask(1, l - 1); int res = 0; for(int i = r; i >= 1; i -= i & -i) res += tree[i]; return res; } vector<int> g[MAX]; int c[MAX]; int par[MAX]; void solve(){ cin >> n; vector<pii> v; for(int i = 1; i <= n; i++){ cin >> c[i]; v.push_back({c[i], i}); } sort(v.begin(), v.end()); int t = 0; for(int i = 0; i < v.size(); i++){ if(i == 0 || v[i].first != v[i - 1].first) t++; c[v[i].second] = t; } par[1] = 1; for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; par[v] = u; int ans = 0; while(1){ ans += ask(1, c[u] - 1); update(c[u], 1); c[u] = c[v]; if(u == 1) break; u = par[u]; } init(); cout << ans << '\n'; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; while(t--){ solve(); } }

Compilation message (stderr)

construction.cpp: In function 'void solve()':
construction.cpp:43:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...