제출 #44383

#제출 시각아이디문제언어결과실행 시간메모리
44383BruteforcemanConstruction of Highway (JOI18_construction)C++11
16 / 100
1073 ms37864 KiB
#include "bits/stdc++.h" using namespace std; typedef pair <int, int> pii; int l[100010], r[100010]; int c[100010]; int n; vector <int> g[100010]; int sub[100010]; int big[100010]; int head[100010]; int pos[100010]; void dfs(int x) { big[x] = -1; sub[x] = 1; for(auto i : g[x]) { dfs(i); sub[x] += sub[i]; if(big[x] == -1 || sub[big[x]] < sub[i]) { big[x] = i; } } } int mx[100010 * 4]; int mn[100010 * 4]; int prop[100010 * 4]; int par[100010]; int dp[20][100010]; const int logn = 19; void pushdown(int c) { if(prop[c] == -1) return ; int l = c << 1; int r = l + 1; prop[l] = prop[r] = prop[c]; mx[l] = mx[r] = prop[c]; mn[l] = mn[r] = prop[c]; prop[c] = -1; } void update(int x, int y, int val, int c = 1, int b = 1, int e = n) { if(x <= b && e <= y) { mn[c] = mx[c] = val; prop[c] = val; return ; } if(y < b || e < x) return ; pushdown(c); int m = (b + e) >> 1; int l = c << 1; int r = l + 1; update(x, y, val, l, b, m); update(x, y, val, r, m+1, e); mn[c] = min(mn[l], mn[r]); mx[c] = max(mx[l], mx[r]); } int query(int x, int val, int c = 1, int b = 1, int e = n) { if(mx[c] == mn[c]) { return mx[c] == val ? x - b + 1 : 0; } if(b == e) return mx[c] == val; pushdown(c); int m = (b + e) >> 1; int l = c << 1; int r = l + 1; if(x <= m) return query(x, val, l, b, m); else { int len = query(x, val, r, m + 1, e); if(x - m == len) { return query(m, val, l, b, m) + len; } else { return len; } } } int queryMin(int x, int y, int c = 1, int b = 1, int e = n) { if(x <= b && e <= y) return mn[c]; if(y < b || e < x) return INT_MAX; pushdown(c); int m = (b + e) >> 1; int l = c << 1; int r = l + 1; return min(queryMin(x, y, l, b, m), queryMin(x, y, r, m+1, e)); } int queryMax(int x, int y, int c = 1, int b = 1, int e = n) { if(x <= b && e <= y) return mx[c]; if(y < b || e < x) return INT_MIN; pushdown(c); int m = (b + e) >> 1; int l = c << 1; int r = l + 1; return max(queryMax(x, y, l, b, m), queryMax(x, y, r, m+1, e)); } int search(int b, int e, int idx) { if(b == e) { return idx - b + 1; } int m = (b + e) >> 1; if(queryMin(m, idx) == queryMax(m, idx)) return search(b, m, idx); else return search(m + 1, e, idx); } int get(int x, int c = 1, int b = 1, int e = n) { if(b == e) return mx[c]; pushdown(c); int m = (b + e) >> 1; int l = c << 1; int r = l + 1; if(x <= m) return get(x, l, b, m); else return get(x, r, m+1, e); } void precalc() { memset(prop, -1, sizeof prop); int cur = 0; for(int i = 1; i <= n; i++) { if(par[i] == -1 || big[par[i]] != i) { for(int j = i; j != -1; j = big[j]) { pos[j] = ++cur; head[j] = i; } } } for(int i = 1; i <= n; i++) { update(pos[i], pos[i], c[i]); } dp[0][1] = 0; for(int i = 2; i <= n; i++) dp[0][i] = par[i]; for(int i = 1; i <= logn; i++) { for(int j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][dp[i - 1][j]]; } } } void change(int x) { int cur = x; while(cur != -1) { update(pos[head[cur]], pos[cur], c[x]); cur = head[cur]; cur = par[cur]; } } int lift(int node, int up) { for(int i = logn; i >= 0; i--) { if((1 << i) <= up) { node = dp[i][node]; up -= 1 << i; } } return node; } long long inverse(vector <pii> v) { long long ans = 0; for(int i = 0; i < v.size(); i++) { for(int j = i + 1; j < v.size(); j++) { if(v[i].first < v[j].first) ans += 1LL * v[i].second * v[j].second; } } return ans; } long long getCost(int x) { vector <pii> v; int cur = par[x]; while(cur > 0) { int val = get(pos[cur]); int len = search(pos[head[cur]], pos[cur], pos[cur]); // query(pos[cur], val); v.push_back(pii(val, len)); while(len--) cur = par[cur]; } return inverse(v); } int main(int argc, char const *argv[]) { scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &c[i]); } par[1] = -1; for(int i = 1; i < n; i++) { scanf("%d %d", &l[i], &r[i]); g[l[i]].push_back(r[i]); par[r[i]] = l[i]; } dfs(1); precalc(); for(int i = 1; i < n; i++) { printf("%lld\n", getCost(r[i])); change(r[i]); } return 0; }

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

construction.cpp: In function 'long long int inverse(std::vector<std::pair<int, int> >)':
construction.cpp:159:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
construction.cpp:160:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i + 1; j < v.size(); j++) {
                      ~~^~~~~~~~~~
construction.cpp: In function 'int main(int, const char**)':
construction.cpp:179:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
construction.cpp:181:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c[i]);
   ~~~~~^~~~~~~~~~~~~
construction.cpp:185:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &l[i], &r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...