Submission #47409

#TimeUsernameProblemLanguageResultExecution timeMemory
47409daniel_02Construction of Highway (JOI18_construction)C++17
16 / 100
240 ms956 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define ppb pop_back #define pf push_front #define ppf pop_front using namespace std; const int N = 4000 + 7; const int inf = 4000+7; int a[N], pr[N]; int t[N]; int cnt; deque<int>dq; void update (int r) { for (; r > 0; r -= (r & -r)) t[r] ++; } int get (int r) { int res = 0; for (; r < N; r += (r & -r)) res += t[r]; return res; } void dfs(int v) { while (v != 0) { dq.pf(a[v]); v = pr[v]; } } void conquer(int v) { ll ans = 0; dfs(v); cnt = 1; for (int i = 0; i < dq.size(); i++) { ans += get(dq[i] + 1); update(dq[i]); } // for (int i = 0; i < dq.size(); i++) // update(1, 1, inf, dq[i], -inf); memset(t, 0, sizeof(t)); dq.clear(); printf("%lld\n", ans); } void upd(int v, int x) { while (v != 0) { a[v] = x; v = pr[v]; } } vector <int> vec; main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); vec.pb(a[i]); } sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end()); for (int i = 1; i <= n; i ++) { a[i] = lower_bound(vec.begin(),vec.end(),a[i]) - vec.begin() + 1; } for (int i = 1; i < n; i++) { int q, w; scanf("%d%d", &q, &w); if (i == 1) { puts("0"); pr[w] = q; a[q] = a[w]; continue; } conquer(q); upd(q, a[w]); pr[w] = q; } }

Compilation message (stderr)

construction.cpp: In function 'void conquer(int)':
construction.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < dq.size(); i++)
                     ~~^~~~~~~~~~~
construction.cpp: At global scope:
construction.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
construction.cpp: In function 'int main()':
construction.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
construction.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &q, &w);
         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...