제출 #506554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
506554		pokmui9909	통행료 (APIO13_toll)	C++14	0 / 100	3 ms	6604 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define x first
#define y second
class UnionFind{
public:
    UnionFind(ll S){
        p.resize(S + 5, -1);
    }
    ll Find(ll n){
        if (p[n] < 0) return n;
        else return p[n] = Find(p[n]);
    }
    void Union(ll a, ll b){
        a = Find(a), b = Find(b);
        if (a == b) return;
        p[b] += p[a];
        p[a] = b;
    }
    bool Same(ll a, ll b) { return Find(a) == Find(b); }
private:
    vector<ll> p;
};
ll N, M, K;
vector<vector<pair<ll, ll>>> T(100005);
struct Edge{
    ll u, v, c;
    bool operator<(const Edge &r)const{
        return c < r.c;
    }
};
vector<Edge> E;
vector<pair<ll, ll>> add;
ll P[100005];
ll Size[100005];
ll depth[100005];
struct MyStruct{
    ll n, c, f;
};
vector<vector<MyStruct>> G(100005);
ll sum = 0, ans = 0;
ll MinCost[100005];
void dfs(ll u, ll p){
    Size[u] = P[u];
    for(auto i : G[u]){
        ll v = i.n, c = i.c, f = i.f;
        if(v == p) continue;
        dfs(v, u);
        Size[u] += Size[v];
        sum += f * c * Size[v];
    }
}
void init(){
    fill(depth, depth + 100005, -1);
    fill(MinCost, MinCost + 100005, 1e18);
    queue<ll> Q;
    depth[1] = 0;
    Q.push(1);
    while(!Q.empty()){
        ll u = Q.front(); Q.pop();
        for(auto v : T[u]){
            if(depth[v.x] != -1) continue;
            depth[v.x] = depth[u] + 1;
            Q.push(v.x);
        }
    }
    for(int i = 0; i < M; i++){
        if(depth[E[i].u] > depth[E[i].v]){
            swap(depth[E[i].u], depth[E[i].v]);
        }
    }
    for(int i = 0; i < K; i++){
        if(depth[add[i].x] > depth[add[i].y]){
            swap(depth[add[i].x], depth[add[i].y]);
        }
    }
    MinCost[1] = 0;
    for(int i = 1; i <= N; i++){
        for(auto j : T[i]){
            if(depth[i] <= depth[j.x]) continue;
            MinCost[i] = min(MinCost[i], j.y);
        }
    }
}
 
int main(){
    cin.tie(0) -> sync_with_stdio(false);
  
    cin >> N >> M >> K;
    for(int i = 1; i <= M; i++){
        ll u, v, c; cin >> u >> v >> c;
        T[u].push_back({v, c});
        T[v].push_back({u, c});
        E.push_back({u, v, c});
    }
    for(int i = 1; i <= K; i++){
        ll u, v; cin >> u >> v;
        add.push_back({u, v});
    }
    for(int i = 1; i <= N; i++){
        cin >> P[i];
    }
    init();
    sort(E.begin(), E.end());
    if(N == 1){
        cout << 0;
        return 0;
    }
    for(int i = 3; i < 4; i++){
        for(int j = 1; j <= N; j++){
            Size[j] = 0;
            G[j].clear();
        }
        UnionFind uf(N);
        ll ok = 1;
        vector<Edge> V;
        for(int j = 0; j < K; j++){
            if(i & (1 << j)){
                ll u = add[j].x, v = add[j].y;
                if(uf.Same(u, v)){
                    ok = 0;
                    break;
                } else {
                    uf.Union(u, v);
                    V.push_back({u, v, MinCost[v]});
                }
            }
        }
        if(!ok) continue;
        vector<Edge> MST;
        for(int j = 0; j < M; j++){
            ll u = E[j].u, v = E[j].v, c = E[j].c;
            if(!uf.Same(u, v)){
                uf.Union(u, v);
                MST.push_back({u, v, c});
            }
        }
        for(int j = 0; j < V.size(); j++){
            ll u = V[j].u, v = V[j].v, c = V[j].c;
            G[u].push_back({v, c, 1});
            G[v].push_back({u, c, 1});
            //cout << u << ' ' << v << ' '<< c << '\n';
        }
        //cout << "\n\n\n";
        for(int j = 0; j < MST.size(); j++){
            ll u = MST[j].u, v = MST[j].v, c = MST[j].c;
            G[u].push_back({v, c, 0});
            G[v].push_back({u, c, 0});
            //cout << u << ' ' << v << ' '<< c << '\n';
        }
        sum = 0;
        dfs(1, -1);
        ans = max(ans, sum);
    }
    cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'int main()':
toll.cpp:140:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         for(int j = 0; j < V.size(); j++){
      |                        ~~^~~~~~~~~~
toll.cpp:147:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for(int j = 0; j < MST.size(); j++){
      |                        ~~^~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22