| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 71578 |
2018-08-25T07:28:29 Z |
강태규(#2217) |
Logistical Metropolis (KRIII5_LM) |
C++11 |
|
1112 ms |
39308 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
int n, m;
vector<int> edge[100001];
llong mstCost;
llong ans[100001];
struct _es {
int x, y, c;
void scan() {
scanf("%d%d%d", &x, &y, &c);
edge[x].push_back(y);
edge[y].push_back(x);
ans[x] += c;
ans[y] += c;
}
bool operator<(const _es &p) const {
return c < p.c;
}
} es[300000];
namespace uf {
int par[100001];
int find(int x) {
if (par[x]) return par[x] = find(par[x]);
return x;
}
int merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return 0;
par[y] = x;
return 1;
}
}
struct _edge {
int x, c;
_edge(int x, int c) : x(x), c(c) {}
};
vector<_edge> treeEdge[100001];
int par[100001][20];
int mx[100001][20];
int dep[100001];
int st[100001];
int ed[100001];
void dfs(int x, int p) {
static int ord = 0;
st[x] = ++ord;
for (int i = 1; i < 20; ++i) {
par[x][i] = par[par[x][i - 1]][i - 1];
mx[x][i] = max(mx[x][i - 1], mx[par[x][i - 1]][i - 1]);
}
for (_edge i : treeEdge[x]) {
if (i.x == p) continue;
dep[i.x] = dep[x] + 1;
par[i.x][0] = x;
mx[i.x][0] = i.c;
dfs(i.x, x);
}
ed[x] = ord;
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; i--; ) {
if ((dep[x] - dep[y]) >> i) x = par[x][i];
}
if (x == y) return x;
for (int i = 20; i--; ) {
if (par[x][i] != par[y][i]) {
x = par[x][i];
y = par[y][i];
}
}
return par[x][0];
}
void getMst() {
sort(es, es + m);
for (int i = 0; i < m; ++i) {
int x = es[i].x;
int y = es[i].y;
int c = es[i].c;
if (uf::merge(x, y)) {
mstCost += c;
treeEdge[x].emplace_back(y, c);
treeEdge[y].emplace_back(x, c);
}
}
dfs(1, 0);
}
void sortVs(vector<int> &v) {
sort(v.begin(), v.end(), [&](int i, int j) { return st[i] < st[j]; });
v.erase(unique(v.begin(), v.end()), v.end());
}
int getDist(int x, int p) {
int ret = 0;
for (int i = 20; i--; ) {
if ((dep[x] - dep[p]) >> i) {
ret = max(ret, mx[x][i]);
x = par[x][i];
}
}
return ret;
}
const llong inf = 1e18;
int ch[100001];
llong dp[100001][2];
void dfsCompress(const vector<int> &vs, int &i) {
int x = vs[i];
if (ch[x]) dp[x][0] = -inf, dp[x][1] = 0;
else dp[x][0] = 0, dp[x][1] = -inf;
for (++i; i < vs.size(); ++i) {
int v = vs[i];
if (ed[x] < st[v]) break;
dfsCompress(vs, i);
int d = getDist(v, x);
llong val = max(dp[v][0], dp[v][1] + d);
dp[x][1] = max(dp[x][1] + val, dp[x][0] + dp[v][1]);
dp[x][0] += val;
}
}
llong solve(int x) {
vector<int> vs;
vs.push_back(x);
ch[x] = 1;
for (int i : edge[x]) {
vs.push_back(i);
ch[i] = 1;
}
sortVs(vs);
int sz = vs.size();
for (int i = 1; i < sz; ++i) {
vs.push_back(lca(vs[i - 1], vs[i]));
}
sortVs(vs);
int ord = 0;
dfsCompress(vs, ord);
for (int i : vs) ch[i] = 0;
return dp[vs[0]][1];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
es[i].scan();
}
getMst();
for (int i = 1; i <= n; ++i) {
printf("%lld\n", mstCost + ans[i] - solve(i));
}
return 0;
}
Compilation message
LM.cpp: In function 'void dfsCompress(const std::vector<int>&, int&)':
LM.cpp:136:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (++i; i < vs.size(); ++i) {
~~^~~~~~~~~~~
LM.cpp: In function 'int main()':
LM.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
LM.cpp: In member function 'void _es::scan()':
LM.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1112 ms |
39308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
