oj.uz

Submission #248507

# Submission time Handle Problem Language Result Execution time Memory
248507 2020-07-12T14:42:16 Z sealnot123 Toll (APIO13_toll) C++14
100 / 100
 1990 ms 15712 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define iFOR(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;

const int N = 100005, M = 300005, K = 50;
int n, m, k;
vector<int> g[N];
int comp[N], n_comp;
// tuple sucks
vector< pair<int, PII> > all_edge;
vector< PII > K_edge;
int MST[M], dsu[N], MUST[M];
vector<int> try_edge;
LL people[N], small_people[K+5];
int find(int i){
    if(i == dsu[i]) return i;
    return dsu[i] = find(dsu[i]);
}
void dfs(int u = 1, int p = 1){
    small_people[comp[u]] += people[u];
    for(int e : g[u]){
        if(abs(e) == p) continue;
        if(e < 0){
            e = -e;
            comp[e] = ++n_comp;
        }else{
            comp[e] = comp[u];
        }
        dfs(e, u);
    }
}
vector<PII> small_g[K+5];
int Max[K+5], edge_idx[K+5];
int parent[K+5], depth[K+5];
int not_choose[K+5];
LL dp_people[K+5];
void make_parent(int u=1, int p=1){
    dp_people[u] = small_people[u];
    for(PII &e : small_g[u]){
        if(e.x == p) continue;
        //printf("(%d, %d)\n",u,e.x);
        parent[e.x] = u;
        depth[e.x] = depth[u]+1;
        edge_idx[e.x] = e.y;
        make_parent(e.x, u);
        dp_people[u] += dp_people[e.x];
    }
}
void play(LL &ans){
    //puts("play reached");
    for(int e : try_edge){
        auto &f = all_edge[e].y;
        f.x = comp[f.x];
        f.y = comp[f.y];
        //assert(f.x != f.y);
    }
    for(PII &e : K_edge){
        e.x = comp[e.x];
        e.y = comp[e.y];
        //assert(e.x != e.y);
    }
    edge_idx[1] = -1;
    FOR(mask, 1, (1<<k)-1){
        memset(not_choose, 0, sizeof not_choose);
        FOR(i, 1, n_comp) dsu[i] = i, Max[i] = (1<<30);
        FOR(i, 0, k-1){
            if(mask & (1<<i)){
                PII &e = K_edge[i];
                //printf("xx(%d, %d)",e.x,e.y);
                if(find(e.x) != find(e.y)){
                    //printf("add (%d, %d)\n",e.x,e.y);
                    dsu[find(e.x)] = find(e.y);
                    small_g[e.x].pb(PII(e.y, i));
                    small_g[e.y].pb(PII(e.x, i));
                }
            }
        }
        //puts("====");
        FOR(i, 0, SZ(try_edge)-1){
            PII &e = all_edge[try_edge[i]].y;
            //printf("try (%d, %d)\n",e.x,e.y);
            if(find(e.x) != find(e.y)){
                dsu[find(e.x)] = find(e.y);
                //printf("add (%d, %d)\n",e.x,e.y);
                small_g[e.x].pb(PII(e.y, -1));
                small_g[e.y].pb(PII(e.x, -1));
            }else{
                not_choose[i] = 1;
            }
        }
        make_parent();
        FOR(i, 0, SZ(try_edge)-1){
            if(not_choose[i] == 0) continue;
            PII &e = all_edge[try_edge[i]].y;
            int v = all_edge[try_edge[i]].x;
            int a = e.x, b = e.y;
            //printf("(%d, %d) v = %d\n",a,b,v);
            while(a != b){
                if(depth[a] < depth[b]) swap(a,b);
                Max[a] = min(Max[a], v);
                //printf("move %d -- %d\n",Max[a]);
                a = parent[a];
            }
        }
        LL sum = 0;
        //FOR(i, 1, n_comp) printf("{%lld} ",dp_people[i]); puts("");
        FOR(i, 1, n_comp){
            if(edge_idx[i] >= 0) sum += dp_people[i] * Max[i];
            small_g[i].clear();
        }
        //printf("sum = %lld\n",sum);
        ans = max(ans, sum);
    }
}
void solve(){
    scanf("%d %d %d",&n,&m,&k);
    FOR(i, 1, m){
        int a, b, c;
        scanf("%d %d %d",&a,&b,&c);
        all_edge.pb({c,PII(a,b)});
    }
    sort(all(all_edge));
    FOR(i, 1, n) dsu[i] = i;
    FOR(i,0,SZ(all_edge)-1){
        auto &e = all_edge[i];
        int a = e.y.x, b = e.y.y;
        if(find(a) != find(b)){
            MST[i] = 1;
            dsu[find(a)] = find(b);
        }
    }
    FOR(i,1,k){
        int a, b;
        scanf("%d %d",&a,&b);
        K_edge.pb(PII(a,b));
    }
    FOR(i,1,n) scanf("%lld",&people[i]);
    //puts("input success");
    FOR(i, 1, n) dsu[i] = i;
    FOR(i, 0, SZ(K_edge)-1){
        auto &e = K_edge[i];
        if(find(e.x) != find(e.y)){
            dsu[find(e.x)] = find(e.y);
            g[e.x].pb(-e.y);
            g[e.y].pb(-e.x);
        }
    }
    FOR(i, 0, SZ(all_edge)-1){
        auto &e = all_edge[i];
        int a = e.y.x, b = e.y.y;
        if(find(a) != find(b)){
            MUST[i] = 1;
            dsu[find(a)] = find(b);
            g[a].pb(b);
            g[b].pb(a);
        }
    }
    //puts("Obtain MUST edges");
    comp[1] = ++n_comp;
    dfs();
    //puts("Generate component + small people success");
    //printf("comp : "); FOR(i,1,n) printf("%d ",comp[i]); puts("");
    FOR(i, 0, SZ(all_edge)-1){
        if(MST[i] && MUST[i] == 0) try_edge.pb(i);
    }
    LL ans = 0;
    play(ans);
    printf("%lld",ans);
}

int main(){
    solve();
	return 0;
}
/*
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

Compilation message

toll.cpp: In function 'void solve()':
toll.cpp:134: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:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~
toll.cpp:155:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i,1,n) scanf("%lld",&people[i]);
                ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 3 ms 2736 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 5 ms 2944 KB Output is correct
6 Correct 5 ms 2944 KB Output is correct
7 Correct 285 ms 15712 KB Output is correct
8 Correct 282 ms 14676 KB Output is correct
9 Correct 281 ms 14424 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 3 ms 2736 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 5 ms 2944 KB Output is correct
6 Correct 5 ms 2944 KB Output is correct
7 Correct 285 ms 15712 KB Output is correct
8 Correct 282 ms 14676 KB Output is correct
9 Correct 281 ms 14424 KB Output is correct
10 Correct 1648 ms 14472 KB Output is correct
11 Correct 1964 ms 15640 KB Output is correct
12 Correct 1990 ms 15636 KB Output is correct