제출 #242689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242689		iefnah06	철인 이종 경기 (APIO18_duathlon)	C++98	0 / 100	326 ms	94784 KiB

count_triplets

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

typedef long long ll;

int n, m;
vector<int> C;
int S;

vector<vector<int> > edges;
vector<int> vis;
vector<int> freq;
vector<int> totfreq;

void dfs(int v) {
	vis[v] = 1;
	freq[C[v]] += 1;
	for (size_t j = 0; j < edges[v].size(); j++) {
		int w = edges[v][j];
		if (vis[w]) continue;
		dfs(w);
	}
}

ll base = 0;
vector<ll> delta;

struct node {
	node* c[2];
	int x;
	ll s; // x * (freq - x)

	void upd() {
		s = (c[0] ? c[0]->s : 0) + (c[1] ? c[1]->s : 0);
	}
};

void upd(node* &v, int lx, int rx, int k) {
	if (!v) {
		v = new node();
	}
	if (lx+1 == rx) {
		v->x += 1;
		v->s = ll(v->x) * (freq[lx] - v->x);
	} else {
		if (k < (lx + rx) / 2) {
			upd(v->c[0], lx, (lx + rx) / 2, k);
		} else {
			upd(v->c[1], (lx + rx) / 2, rx, k);
		}
		v->upd();
	}
}

node* merge(node* a, node* b, int lx, int rx, ll& res) {
	if (!a) return b;
	if (!b) return a;
	if (lx+1 == rx) {
		res += ll(a->x) * b->x;
		a->x += b->x;
		a->s = ll(a->x) * (freq[lx] - a->x);
	} else {
		a->c[0] = merge(a->c[0], b->c[0], lx, (lx + rx) / 2, res);
		a->c[1] = merge(a->c[1], b->c[1], (lx + rx) / 2, rx, res);
		a->upd();
	}
	return a;
}

vector<node*> roots;
vector<int> sidx;
int curidx = 0;

int dfs1(int v) {
	sidx[v] = curidx;
	int lowval = curidx;
	curidx++;
	upd(roots[v], 0, S, C[v]);
	node* r2 = NULL;
	for (size_t j = 0; j < edges[v].size(); j++) {
		int w = edges[v][j];
		if (sidx[w] == -1) {
			int wlowval = dfs1(w);
			if (wlowval == sidx[v]) {
				roots[v] = merge(roots[v], roots[w], 0, S, delta[v]);
			} else {
				ll dummy = 0;
				r2 = merge(r2, roots[w], 0, S, dummy);
				lowval = min(lowval, wlowval);
			}
		} else if (sidx[w] < lowval) {
			lowval = sidx[w];
		}
	}
	delta[v] += roots[v]->s;
	ll dummy = 0;
	roots[v] = merge(roots[v], r2, 0, S, dummy);
	return lowval;
}

vector<int> vis2;

void dfs2(int v) {
	vis2[v] = 1;
	if (freq[C[v]]) {
		base += ll(totfreq[C[v]]) * freq[C[v]];
		totfreq[C[v]] += freq[C[v]];
		freq[C[v]] = 0;
	}
	for (size_t j = 0; j < edges[v].size(); j++) {
		int w = edges[v][j];
		if (vis2[w]) continue;
		dfs2(w);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	C.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> C[i];
	}
	{ // 压缩
		vector<int> cval = C;
		sort(cval.begin(), cval.end());
		cval.erase(unique(cval.begin(), cval.end()), cval.end());
		for (int i = 0; i < n; i++) {
			C[i] = int(lower_bound(cval.begin(), cval.end(), C[i]) - cval.begin());
		}
		S = int(cval.size());
	}
	edges.resize(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	vis.assign(n, 0);
	vis2.assign(n, 0);
	freq.assign(S, 0);
	totfreq.assign(S, 0);
	delta.assign(n, 0);
	roots.resize(n);
	sidx.assign(n, -1);
	for (int s = 0; s < n; s++) {
		if (vis[s]) continue;
		dfs(s);
		dfs1(s);
		dfs2(s);
	}
	for (int i = 0; i < n; i++) {
		cout << delta[i] + base << '\n';
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10