Submission #2471658

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, m, val[N], c[N];
vector <int> g[N], newG[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> c[i];

	cin >> m;
	while(m--) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	for (int i = 1; i <= n; ++i) {
		sort(g[i].begin(), g[i].end(), [&](int x, int y) {
			return c[x] < c[y];
		});

		if (g[i].size() == 0) continue;

		vector <int> nw;
		for (int j = 0; j < g[i].size(); ) {
			int curc = c[g[i][j]];
			vector <int> nxt;
			while(j < g[i].size() && c[g[i][j]] == curc) {
				nxt.push_back(g[i][j]);
				++j;
			}
			for (auto &u : nxt) {
				for (auto &v : nw) {
					newG[u].push_back(v); // u -> v
				}
			}
			nw = nxt;
		}

		for (int &j : g[i]) {
			if (c[i] > c[j]) newG[i].push_back(j); // i -> j
		}
	}

	vector < pair<int,int> > vec;
	for (int i = 1; i <= n; ++i) vec.push_back(make_pair(c[i], i));

	sort(vec.begin(), vec.end());

	for (int i = 0; i < vec.size(); ++i) {
		int u = vec[i].second;
		int mx = 0;
		for (int &v : newG[u]) {
			assert(val[v] != 0);
			mx = max(mx, val[v]);
		}
		val[u] = mx + 1;
	}

	// calc sum
	long long sum = 0;
	for (int i = 1; i <= n; ++i) {
		sum += val[i];
		cerr << i << ' ' << val[i] << endl;
	}

	printf("%lld\n", sum);
}

Submission Info

Judge Result