Submission #43697

#	Time	Username	Problem	Language	Result	Execution time	Memory
43697		spencercompton	Toll (APIO13_toll)	C++14	16 / 100	7 ms	2860 KiB

toll

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector<long long> freq;
long long ans;
class Edge{
    public:
        int s, e, c;
        bool my; 
        Edge(int x, int y, int z, bool q){
            s = x;
            e = y;
            c = z;
            my = q;
        }
        bool operator<(const Edge &o) const{
            if(c!=o.c){
                return c<o.c;
            }
            return (my!=o.my?my:false);
        }
};
vector<Edge> edges;
vector<Edge> adj[100000];
pair<long long, long long> go2(int now, int from){
    pair<long long, long long> ret = make_pair(freq[now],0LL);
    for(int i = 0; i<adj[now].size(); i++){
        Edge ed = adj[now][i];
        if(ed.e==from){
            continue;
        }
        pair<long long, long long> got = go2(ed.e,now);
        ret.first += got.first;
        ret.second += got.second + (ed.my?(long long)ed.c*(long long)got.first:0LL);
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 0; i<m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        edges.push_back(Edge(a,b,c, false));
    }
    vector<Edge> other;
    for(int i = 0; i<k; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        other.push_back(Edge(a,b,-1, true));
    }
    for(int i = 0; i<n; i++){
        long long x;
        cin >> x;
        freq.push_back(x);
    }
    bool assigned[k];
    for(int i = 0; i<k; i++){
        assigned[i] = false;
    }
    int comp[n];
    int sz[n];
    ans = 0LL;
    vector<int> li[n];
    for(int i = 0; i<n; i++){
        comp[i] = i;
        sz[i] = 1;
        li[i].push_back(i);
    }
    sort(edges.begin(),edges.end());
    vector<Edge> og;
    for(int i = 0; i<m; i++){
        int ca = comp[edges[i].s];
        int cb = comp[edges[i].e];
        if(ca==cb){
            continue;
        }
        if(sz[ca]>sz[cb]){
            swap(ca,cb);
        }
        //ca < cb
        sz[cb] += sz[ca];
        for(int i = 0; i<li[ca].size(); i++){
            int now = li[ca][i];
            comp[now] = cb;
            li[cb].push_back(now);
        }
        li[ca].clear();
        for(int j = 0; j<k; j++){
            if(!assigned[j] && comp[other[j].s]==comp[other[j].e]){
                assigned[j] = true;
                other[j].c = edges[i].c;
            }
        }
        og.push_back(edges[i]);
    }
    for(int i = 0; i<k; i++){
        assert(assigned[i]);
    }
    for(int z = 0; z<(1<<k); z++){
        vector<Edge> all;
        vector<Edge> used;
        for(int i = 0; i<k; i++){
            if(((1<<i)&z)!=0){
                all.push_back(other[i]);
            }
        }
        for(int i = 0; i<og.size(); i++){
            all.push_back(og[i]);
        }
        sort(all.begin(),all.end());
        for(int i = 0; i<n; i++){
            comp[i] = i;
            sz[i] = 1;
            li[i].clear();
            li[i].push_back(i);
        }
        for(int i = 0; i<all.size(); i++){
            int ca = comp[all[i].s];
            int cb = comp[all[i].e];
            if(ca==cb){
                continue;
            }
            if(sz[ca]>sz[cb]){
                swap(ca,cb);
            }
            //ca < cb
            sz[cb] += sz[ca];
            for(int i = 0; i<li[ca].size(); i++){
                int now = li[ca][i];
                comp[now] = cb;
                li[cb].push_back(now);
            }
            li[ca].clear();
            used.push_back(all[i]);
        }
        for(int i = 0; i<n; i++){
            adj[i].clear();
        }
        
        for(int i = 0; i<used.size(); i++){
            Edge ed = used[i];
            adj[ed.s].push_back(Edge(ed.s,ed.e,ed.c,ed.my));
            adj[ed.e].push_back(Edge(ed.e,ed.s,ed.c,ed.my));
        }
        ans = max(ans,go2(0,-1).second);
    }
    cout << ans << endl;
}

Compilation message (stderr)

toll.cpp: In function 'std::pair<long long int, long long int> go2(int, int)':
toll.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<adj[now].size(); i++){
                     ^
toll.cpp: In function 'int main()':
toll.cpp:88:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i<li[ca].size(); i++){
                         ^
toll.cpp:113:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i<og.size(); i++){
                         ^
toll.cpp:123:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i<all.size(); i++){
                         ^
toll.cpp:134:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i<li[ca].size(); i++){
                             ^
toll.cpp:146:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i<used.size(); i++){
                         ^

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