제출 #999094

#제출 시각아이디문제언어결과실행 시간메모리
999094WhisperConstruction of Highway (JOI18_construction)C++17
0 / 100
186 ms262144 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FORD(i, a, b) for (int i = (b); i >= (a); i --) #define REP(i, n) for (int i = 0; i < (n); ++i) #define REPD(i, n) for (int i = (n) - 1; i >= 0; --i) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) constexpr ll LINF = (1ll << 60); constexpr int INF = (1ll << 30); constexpr int Mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); /* Phu Trong from Nguyen Tat Thanh High School for gifted student */ template <class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) {x = y; return 1;} return 0; } template <class X, class Y> bool maximize(X &x, const Y &y){ X eps = 1e-9; if (x + eps < y) {x = y; return 1;} return 0; } #define MAX 100005 int numNode; struct Edge{ int u, v; Edge(){} Edge(int _u, int _v): u(_u), v(_v){} int other(int x){return (x ^ u ^ v);} } edge[MAX]; vector<int> G[MAX]; int label[MAX]; // label(i) as liveness of i-th city int dep[MAX], head[MAX], heavy[MAX], sz[MAX], pos[MAX], par[MAX]; int cnt = 0; int pre_dfs(int u, int p = -1){ sz[u] = 1; par[u] = p; int bigChild = 0; for (int &i : G[u]){ int v = edge[i].other(u); if(v ^ p){ dep[v] = dep[u] + 1; pre_dfs(v, u); sz[u] += sz[v]; if (sz[bigChild] < sz[v]){ bigChild = v, heavy[u] = v; } } } } deque<pair<int, int>> group[MAX]; void decompose(int u, int p = 1){ pos[u] = ++cnt; group[p].push_back(make_pair(label[u], 1ll)); head[u] = p; if(heavy[u]) decompose(heavy[u], p); for (int &i : G[u]){ int v = edge[i].other(u); if (v ^ par[u]) if(v ^ heavy[u]){ decompose(v, v); //make new chain } } } #define All(x) (x).begin(), (x).end() struct FenwickTree{ int *F = nullptr; int n; vector<pair<int, int>> rollback; void init (int _n = 0){ this -> n = _n; F = new int[n + 5]; fill(F, F + n + 1, 0); } void upd(int p, int val){ if (val > 0) rollback.push_back(make_pair(p, -val)); for (; p > 0; p -= p & (-p)) F[p] += val; } int query(int p){ int res = 0; for (; p <= n; p += p & (-p)) res += F[p]; return res; } void undo(void){ while ((int)rollback.size()){ upd(rollback.back().first, rollback.back().second); rollback.pop_back(); } } } fen; int ans; void addEdge(int u, int v){ vector<pair<int, int>> upd; ans = 0; while (u > 0){ vector<pair<int, int>> nw_upd; int length = dep[u] - dep[head[u]] + 1; while (length > 0 && (int)group[head[u]].size()){ if (length >= group[head[u]].front().second){ length -= group[head[u]].front().second; nw_upd.emplace_back(group[head[u]].front()); group[head[u]].pop_front(); } else{ group[head[u]].front().second -= length; nw_upd.emplace_back(group[head[u]].front().first, length); length = 0; } } group[head[u]].push_front(make_pair(label[v], dep[u] - dep[head[u]] + 1)); reverse(All(nw_upd)); for (auto&j : nw_upd) upd.push_back(j); u = par[head[u]]; } reverse(All(upd)); for (pair<int, int>&x : upd){ int val = x.first, cnt = x.second; ans += fen.query(val + 1) * cnt; fen.upd(val, cnt); } fen.undo(); } void process(void){ cin >> numNode; for (int i = 1; i <= numNode; ++i) cin >> label[i]; for (int i = 1; i < numNode; ++i){ cin >> edge[i].u >> edge[i].v; G[edge[i].u].emplace_back(i); G[edge[i].v].emplace_back(i); } vector<int> comp; for (int i = 1; i <= numNode; ++i) comp.push_back(label[i]); sort(All(comp)); for (int i = 1; i <= numNode; ++i) label[i] = lower_bound(All(comp), label[i]) - comp.begin() + 1; pre_dfs(1); decompose(1); fen.init(numNode); for (int i = 1; i < numNode; ++i){ int u = edge[i].u, v = edge[i].v; addEdge(u, v); cout << ans << '\n'; } } signed main(){ #define name "Whisper" cin.tie(nullptr) -> sync_with_stdio(false); //freopen(name".inp", "r", stdin); //freopen(name".out", "w", stdout); process(); }

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

construction.cpp: In function 'long long int pre_dfs(long long int, long long int)':
construction.cpp:69:1: warning: no return statement in function returning non-void [-Wreturn-type]
   69 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...