Submission #1020526

#TimeUsernameProblemLanguageResultExecution timeMemory
1020526toan2602Untitled (POI11_rot)C++17
0 / 100
1087 ms38472 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int n, x, idx = 1, a[1000005], bit[1000005], subtree[1000005], ans[1000005]; vector<int> adj[1000005]; int RES = 0; void add(int pos, int val) { while(pos <= idx) { bit[pos] += val; pos += pos & -pos; } } int get(int x) { int res = 0; while(x > 0) { res += bit[x]; x -= x & -x; } return res; } int range(int l, int r) {return get(r) - get(l-1);} void build_sub(int u, int par) { subtree[u] = 1; for (int node: adj[u]) { if(node == par) continue; build_sub(node, u); subtree[u] += subtree[node]; } } void build(int u) { cin >> x; if(x == 0) { int l, r; l = idx+1, r = idx+2; idx+=2; adj[u].push_back(l); adj[u].push_back(r); build(l); build(r); } else if(adj[u].size() == 0) a[u] = x; } pair<int,int> dfs2(int u) { pair<int, int> res = {range(a[u]+1,idx), range(1,a[u]-1)}; for (int node: adj[u]) {pair<int, int> val = dfs2(node); res.first+=val.first,res.second+=val.second;} return res; } void dfs(int u) { int mx = 0, p = 0; for (int node: adj[u]) if(mx < subtree[node]) mx = subtree[node], p = node; if(p == 0) { add(a[u],1); return; } dfs(p); if(p == 1) swap(adj[u][0], adj[u][1]), p = 0; pair<int, int> val = dfs2(adj[u][1]); RES += min(val.first, val.second); dfs(adj[u][1]); } void solve() { cin >> n; build(1); n = idx; build_sub(1,-1); dfs(1); cout << RES; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen("input.inp","r")){ freopen("input.inp", "r", stdin); freopen("output.out", "w", stdout); } int t = 1; // cin >> t; while(t--) { solve(); } }

Compilation message (stderr)

rot.cpp: In function 'int main()':
rot.cpp:77:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   freopen("input.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
rot.cpp:78:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   freopen("output.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...