#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';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
326 ms |
94784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
