제출 #529074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529074		8e7	Construction of Highway (JOI18_construction)	C++17	100 / 100	255 ms	21336 KiB

construction

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct BIT{
	ll bit[maxn];
	vector<pii> ch;
	void modify(int ind, int val) {
		ch.push_back({ind, val});
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
	}
	ll query(int ind) {
		ll ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
	void rev() {
		for (auto [ind, val]:ch) {
			for (;ind < maxn;ind += ind & (-ind)) bit[ind] -= val;
		}
		ch.clear();
	}
} bit;

vector<int> adj[maxn];

int c[maxn], par[maxn], siz[maxn], dep[maxn], ti[maxn], up[maxn], ord[maxn];
int nxt[maxn];
void getsiz(int n, int pa, int d) {
	dep[n] = d;
	siz[n] = 1;
	for (int v:adj[n]) {
		getsiz(v, n, d+1);
		siz[n] += siz[v];	
	}
}
void mark(int n, int pa, int vi) {
	up[n] = vi;
	int best = 0, bind = 0;
	for (int v:adj[n]) {
		if (siz[v] > best) {
			best = siz[v], bind = v;
		}
	}
	nxt[n] = bind;
	for (int v:adj[n]) {
		if (v != bind) {
			mark(v, n, v);
		} else {
			mark(v, n, vi);
		}
	}
}
ll ans[maxn];

vector<pii> se[maxn];

int main() {
	io
	int n;
	cin >> n;
	vector<int> val;
	for (int i = 1;i <= n;i++) cin >> c[i], val.push_back(c[i]);		
	sort(val.begin(), val.end());
	val.resize(int(unique(val.begin(), val.end()) - val.begin()));
	for (int i = 1;i <= n;i++) c[i] = (lower_bound(val.begin(), val.end(), c[i]) - val.begin() + 1);	

	for (int i = 1;i <= n - 1;i++) {
		int u, v;
		cin >> u >> v;
		par[v] = u;
		ti[v] = i;
		ord[i] = v;
		adj[u].push_back(v);
	}
	getsiz(1, 0, 0);
	mark(1, 0, 1);
	
	se[1].push_back({0, 1});
	pary(up + 1, up + n + 1);
	for (int id = 1;id <= n - 1;id++) {
		int i = par[ord[id]], nc = c[ord[id]];
		vector<pii> col;
		col.push_back({dep[ord[id]], maxn - 1});
		debug(i);
		while (i) {
			//get all segments into col and update
			int p = up[i], di = dep[i] + 1, last = 0;
			vector<pii> &cur = se[p];
			vector<pii> tmp;
			int siz = cur.size();

			while (siz && cur.back().ff < di) {
				last = cur.back().ss;	
				tmp.push_back(cur.back());	
				cur.pop_back();
				siz--;
			}
			if (ti[nxt[i]] < id && !(siz && cur.back().ff == di)) cur.push_back({di, last});
			cur.push_back({dep[p], nc});

			reverse(tmp.begin(), tmp.end());
			col.insert(col.end(), tmp.begin(), tmp.end());
			for (auto x:cur) debug(x.ff, x.ss);
			i = par[p];
		}
		i = ord[id];
		//debug(col[0].ff, col[0].ss);
		for (int j = 1;j < col.size();j++) {
			//debug(col[j].ff, col[j].ss);
			ans[i] += bit.query(col[j].ss - 1) * (col[j-1].ff - col[j].ff);
			bit.modify(col[j].ss, col[j-1].ff - col[j].ff);
		}
		if (i == up[i]) {
			se[i].push_back({dep[i], c[i]});
		}
		bit.rev();
	}

	for (int i = 1;i <= n - 1;i++) cout << ans[ord[i]] << "\n";
}
/*
7
1 2 3 4 5 6 1
1 2
2 3
3 4
3 5
2 6
4 7

9
1 4 5 2 7 3 6 3 1
1 2
1 3
3 4
4 5
4 6
1 7
2 8
5 9

10
1 5 8 6 7 2 9 3 4 10
1 5
1 8
5 9
8 3
5 4
8 6
9 7
3 10
4 2
*/

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

construction.cpp: In function 'int main()':
construction.cpp:13:19: warning: statement has no effect [-Wunused-value]
   13 | #define pary(...) 0
      |                   ^
construction.cpp:96:2: note: in expansion of macro 'pary'
   96 |  pary(up + 1, up + n + 1);
      |  ^~~~
construction.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
construction.cpp:101:3: note: in expansion of macro 'debug'
  101 |   debug(i);
      |   ^~~~~
construction.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
construction.cpp:120:21: note: in expansion of macro 'debug'
  120 |    for (auto x:cur) debug(x.ff, x.ss);
      |                     ^~~~~
construction.cpp:120:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  120 |    for (auto x:cur) debug(x.ff, x.ss);
      |              ^
construction.cpp:125:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for (int j = 1;j < col.size();j++) {
      |                  ~~^~~~~~~~~~~~

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