제출 #44383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44383		Bruteforceman	Construction of Highway (JOI18_construction)	C++11	16 / 100	1073 ms	37864 KiB

construction

#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]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84