oj.uz

Submission #248502

# Submission time Handle Problem Language Result Execution time Memory
248502 2020-07-12T14:39:58 Z sealnot123 Toll (APIO13_toll) C++14
78 / 100
 2500 ms 16600 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");
    while(n_comp > 20);
    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:135: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:138: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:153: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:156: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 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 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 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 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 291 ms 13784 KB Output is correct
8 Correct 276 ms 16472 KB Output is correct
9 Correct 280 ms 16600 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 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 291 ms 13784 KB Output is correct
8 Correct 276 ms 16472 KB Output is correct
9 Correct 280 ms 16600 KB Output is correct
10 Execution timed out 2583 ms 16476 KB Time limit exceeded
11 Halted 0 ms 0 KB -