제출 #1015633

#제출 시각아이디문제언어결과실행 시간메모리
1015633panConstruction of Highway (JOI18_construction)C++17
0 / 100
33 ms71772 KiB
#include <bits/stdc++.h> //#include "bits_stdc++.h" //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define endl '\n' #define f first #define s second #define pb push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define input(x) scanf("%lld", &x); #define input2(x, y) scanf("%lld%lld", &x, &y); #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z); #define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a); #define print(x, y) printf("%lld%c", x, y); #define show(x) cerr << #x << " is " << x << endl; #define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl; #define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl; #define all(x) x.begin(), x.end() #define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); #define FOR(i, x, n) for (ll i =x; i<=n; ++i) #define RFOR(i, x, n) for (ll i =x; i>=n; --i) using namespace std; mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); //using namespace __gnu_pbds; //#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> //#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> typedef long long ll; typedef long double ld; typedef pair<ld, ll> pd; typedef pair<string, ll> psl; typedef pair<ll, ll> pi; typedef pair<pi, ll> pii; typedef pair<pi, pi> piii; ll n, hld_label = 0; ll const MAXN = 100010; vector<ll> adj[MAXN]; ll depth[MAXN], siz[MAXN], heavyp[MAXN], parent[MAXN], in[MAXN], out[MAXN], val[MAXN], a[MAXN], b[MAXN]; deque<pi> dq[MAXN]; void dfs_size(ll p, ll node) // hld pre-order + subtree size { if (adj[node].size()>=2 && adj[node][0]==p) swap(adj[node][0], adj[node][1]); siz[node]=1; for (auto& u: adj[node]) { if (u==p) continue; depth[u] = depth[node]+1; parent[u] = node; dfs_size(node, u); siz[node] += siz[u]; if (siz[u]>siz[adj[node][0]]) swap(adj[node][0], u); // order heavy edge together } } // heavyp = next ancester with conseutive path (as in sgtree) to current node void dfs_hld(ll p, ll node) { hld_label++; in[node] = hld_label; dq[heavyp[node]].pb(mp(val[node], 1)); for (ll u: adj[node]) { if (u==p) continue; if (u==adj[node][0]) heavyp[u] = heavyp[node]; // trace the topmost vertice in the path else heavyp[u] = u; // for light vertice, this is simply itself dfs_hld(node, u); } out[node] = hld_label; } // BIT vector<ll> dis; vector<ll> fenwick(MAXN,0); ll ps(ll i) { if (i==0) return 0; ll sum=0; while (i>0) { sum+=fenwick[i]; i-=i&(-i); } return sum; } void update(ll i, ll v) { while (i<=100005) { fenwick[i]+=v; i+=i&(-i); } } int main() { input(n); for (ll i=1; i<=n; ++i) {input(val[i]); dis.pb(val[i]);} discretize(dis); for (ll i=1; i<=n; ++i) {val[i] = lb(all(dis), val[i])-dis.begin() + 1;} for (ll i=1; i<=n-1; ++i) { input2(a[i], b[i]); adj[a[i]].pb(b[i]); } parent[1] = -1; depth[1] = 0; heavyp[1] = 1; dfs_size(-1, 1); dfs_hld(-1, 1); for (ll i=1; i<=n-1; ++i) { //show(i); ll ans = 0; ll now = a[i]; vector<pi> undo; while (now!=-1) { //show(now); vector<pi> qq; ll cnt = depth[now] - depth[heavyp[now]] +1; while (dq[heavyp[now]].size() && cnt) { ll take = min(dq[heavyp[now]].front().s, cnt); //show2(dq[heavyp[now]].front().f, dq[heavyp[now]].front().s); cnt-=take; dq[heavyp[now]].front().s-=take; ll idx = lb(all(dis), dq[heavyp[now]].front().f)-dis.begin() + 1; //ans += ps(idx-1)*take; //update(idx, take); qq.pb(mp(idx, take)); if (dq[heavyp[now]].front().s ==0) dq[heavyp[now]].pop_front(); } dq[heavyp[now]].push_front(mp(val[b[i]], depth[now] - depth[heavyp[now]] +1)); now = parent[heavyp[now]]; reverse(all(qq)); for (pi u: qq) ans += ps(u.f-1)*u.s, update(u.f, u.s), undo.pb(u); } for (pi u: undo) update(u.f, -u.s); print(ans, '\n'); } return 0; }

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

construction.cpp: In function 'int main()':
construction.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
construction.cpp:101:2: note: in expansion of macro 'input'
  101 |  input(n);
      |  ^~~~~
construction.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
construction.cpp:102:27: note: in expansion of macro 'input'
  102 |  for (ll i=1; i<=n; ++i) {input(val[i]); dis.pb(val[i]);}
      |                           ^~~~~
construction.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
construction.cpp:107:3: note: in expansion of macro 'input2'
  107 |   input2(a[i], b[i]);
      |   ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...