oj.uz

Submission #99073

# Submission time Handle Problem Language Result Execution time Memory
99073 2019-02-28T09:33:08 Z Akashi Toll (APIO13_toll) C++14
100 / 100
 2005 ms 20860 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 6 ms 2736 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 6 ms 2736 KB Output is correct
5 Correct 8 ms 2816 KB Output is correct
6 Correct 9 ms 2944 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 6 ms 2736 KB Output is correct
5 Correct 8 ms 2816 KB Output is correct
6 Correct 9 ms 2944 KB Output is correct
7 Correct 356 ms 14836 KB Output is correct
8 Correct 350 ms 20860 KB Output is correct
9 Correct 373 ms 20824 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 6 ms 2736 KB Output is correct
5 Correct 8 ms 2816 KB Output is correct
6 Correct 9 ms 2944 KB Output is correct
7 Correct 356 ms 14836 KB Output is correct
8 Correct 350 ms 20860 KB Output is correct
9 Correct 373 ms 20824 KB Output is correct
10 Correct 1692 ms 20836 KB Output is correct
11 Correct 2005 ms 20860 KB Output is correct
12 Correct 1902 ms 20860 KB Output is correct