Submission #71559

# Submission time Handle Problem Language Result Execution time Memory
71559 2018-08-25T07:01:41 Z 강태규(#2217) Logistical Metropolis (KRIII5_LM) C++11
0 / 7
1300 ms 38760 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;
    else dp[x][0] = 0;
    dp[x][1] = 0;
    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][0] += val;
        dp[x][1] = max(dp[x][1] + val, dp[x][0] + dp[v][1]);
    }
}

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:137: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:172: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 17 ms 5496 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1300 ms 38760 KB Output isn't correct
2 Halted 0 ms 0 KB -