oj.uz

답안 #242689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242689 2020-06-29T02:46:37 Z iefnah06 철인 이종 경기 (APIO18_duathlon) C++
0 / 100
 326 ms 94784 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 326 ms 94784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 81 ms 13292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 66 ms 12400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -