Submission #99073

#	Time	Username	Problem	Language	Result	Execution time	Memory
99073		Akashi	Toll (APIO13_toll)	C++14	100 / 100	2005 ms	20860 KiB

toll

#include <bits/stdc++.h>
using namespace std;

struct edge{
    int x, y, k, i;
    bool operator < (const edge &aux)const{
        if(k != aux.k) return k < aux.k;
        return i < aux.i;
    }
};

struct dsu{
    int tt[100005], RG[100005];
    void ini(int n){
        for(int i = 1; i <= n ; ++i)
            tt[i] = i, RG[i] = 1;
    }
    inline int Find(int x){
        int R = x;
        while(R != tt[R]) R = tt[R];
        while(x != tt[x]){
            int aux = tt[x];
            tt[x] = R; x = aux;
        }
        return R;
    }
    inline void Union(int x, int y){
        if(RG[x] > RG[y]) tt[y] = x;
        else if(RG[x] < RG[y]) tt[x] = y;
        else{
            ++RG[x];
            tt[y] = x;
        }
    }
};
dsu D;

edge a[310005], b[25];
vector <edge> sv;
vector <edge> v[100005];
vector <edge> v2[25];
bool val[25];
int TT[25], h[25], pr[25];
long long sum[25], p[25];

int nrp[100005], tag[100005];
bool ch[310000];
int n, m, k, NR;

inline void precomp(){
    D.ini(n);

    sort(a + 1, a + m + 1);
    for(int i = 1; i <= m ; ++i){
        if(D.Find(a[i].x) != D.Find(a[i].y)){
            D.Union(D.Find(a[i].x), D.Find(a[i].y));
            ch[a[i].i] = 1;
        }
    }

    for(int i = 1; i <= k ; ++i){
        b[i].i = m + i;
        b[i].k = 0;
        a[++m] = b[i];
    }

    sort(a + 1, a + m + 1);
    D.ini(n);
    for(int i = 1; i <= m ; ++i){
        if(D.Find(a[i].x) != D.Find(a[i].y)){
            D.Union(D.Find(a[i].x), D.Find(a[i].y));
            if(ch[a[i].i]){
                v[a[i].x].push_back(a[i]);
                v[a[i].y].push_back({a[i].y, a[i].x, a[i].k, a[i].i});
            }
            ch[a[i].i] = 0;
        }
    }

    for(int i = 1; i <= m ; ++i)
        if(ch[a[i].i]) sv.push_back(a[i]);
}

void dfs(int nod){
    p[tag[nod]] += nrp[nod];
    for(auto it : v[nod]){
        if(tag[it.y]) continue ;
        tag[it.y] = tag[nod];
        dfs(it.y);
    }
}

void dfs2(int nod){
    sum[nod] = p[nod];
    for(auto it : v2[nod]){
        if(TT[it.x] == it.y) continue ;

        TT[it.y] = it.x;
        h[it.y] = h[it.x] + 1;

        dfs2(it.y);

        sum[it.x] += sum[it.y];

        if(it.i == 1) val[it.y] = 1;
    }
}

inline long long solve(int mask){
    for(int i = 1; i <= NR ; ++i) v2[i].clear();
    memset(val, 0, sizeof(val));
    memset(sum, 0, sizeof(sum));
    memset(pr, 0x3f, sizeof(pr));

    D.ini(NR);
    for(int i = 1; i <= k ; ++i){
        if(((1 << (i - 1)) & mask)){
            if(D.Find(b[i].x) == D.Find(b[i].y)) return -1;
            D.Union(D.Find(b[i].x), D.Find(b[i].y));
            v2[b[i].x].push_back({b[i].x, b[i].y, 0, 1});
            v2[b[i].y].push_back({b[i].y, b[i].x, 0, 1});
        }
    }

    vector <edge> nv;
    for(auto it : sv){
        if(D.Find(it.x) != D.Find(it.y)){
            D.Union(D.Find(it.x), D.Find(it.y));
            v2[it.x].push_back({it.x, it.y, 0, 0});
            v2[it.y].push_back({it.y, it.x, 0, 0});
        }
        else nv.push_back(it);
    }

    dfs2(1);
    for(auto it : nv){
        int x = it.x, y = it.y, k = it.k;
        if(h[x] < h[y]) swap(x, y);

        while(h[x] != h[y]){
            pr[x] = min(pr[x], k);
            x = TT[x];
        }
        while(x != y){
            pr[x] = min(pr[x], k);
            pr[y] = min(pr[y], k);
            x = TT[x]; y = TT[y];
        }
    }
    long long ans = 0;
    for(int i = 2; i <= NR ; ++i)
        if(val[i]) ans += 1LL * sum[i] * pr[i];
    return ans;
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d%d", &n, &m, &k);

    for(int i = 1; i <= m ; ++i)
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].k), a[i].i = i;

    for(int i = 1; i <= k ; ++i)
        scanf("%d%d", &b[i].x, &b[i].y);

    precomp();

    for(int i = 1; i <= n ; ++i) scanf("%d", &nrp[i]);
    for(int i = 1; i <= n ; ++i){
        if(tag[i]) continue ;
        tag[i] = ++NR;
        dfs(i);
    }

    for(auto &it : sv) it.x = tag[it.x], it.y = tag[it.y];

    sort(sv.begin(), sv.end());

    for(int i = 1; i <= k ; ++i) b[i].x = tag[b[i].x], b[i].y = tag[b[i].y];

    long long Sol = 0;
    for(int i = 1; i < (1 << k) ; ++i) Sol = max(Sol, solve(i));

    printf("%lld", Sol);

    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:160:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:163:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].k), a[i].i = i;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
toll.cpp:166:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &b[i].x, &b[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:170:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n ; ++i) scanf("%d", &nrp[i]);
                                  ~~~~~^~~~~~~~~~~~~~~

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