Submission #73930

# Submission time Handle Problem Language Result Execution time Memory
73930 2018-08-29T09:38:03 Z ainta Toll (APIO13_toll) C++17
100 / 100
2330 ms 19180 KB
#include<stdio.h>
#include<algorithm>
#include<list>
#define N_ 101000
#define LIT list<Edge3>::iterator
using namespace std;
int N, M, K, Renum[N_], C, P[N_];
long long SZ[30], Res;
struct Edge{
    int a, b, c;
    bool operator <(const Edge &p)const{
        return c < p.c;
    }
}Ed[301000];
 
struct Edge2{
    int a, b;
}w[30];
 
struct Edge3{
    int a, b, gap;
    bool ck;
}tp, par2[N_], def_E[30];
list <Edge3> E[N_];
 
int par[N_];
 
int find(int a){
    if (a == par[a])return a;
    return par[a] = find(par[a]);
}
 
void init(){
    int i, x, y;
    for (i = 1; i <= N; i++){
        par[i] = i;
    }
    for (i = 0; i < M; i++){
        x = find(Ed[i].a), y = find(Ed[i].b);
        if (x == y)continue;
        par[x] = y;
        tp.a = Ed[i].a, tp.b = Ed[i].b, tp.gap = Ed[i].c, tp.ck = false;
        E[Ed[i].a].push_back(tp);
        tp.a = Ed[i].b, tp.b = Ed[i].a;
        E[Ed[i].b].push_back(tp);
    }
}
 
int Q[N_];
 
void BFS(int a){
    int h = 0, t = 0, x;
    LIT it;
    Q[++t] = a, par2[a].a = a;
    while (h < t){
        x = Q[++h];
        for (it = E[x].begin(); it!=E[x].end(); it++){
            if (!par2[it->b].a){
                Q[++t] =it->b;
                par2[it->b] = *it;
            }
        }
    }
}
int cnt;
void Modify(int a, int b, int c){
    LIT it;
    for (it = E[a].begin(); it!=E[a].end(); it++){
        if (it->b == b){
            if (c == -1){
                E[a].erase(it);
                break;
            }
            else it->gap = c;
        }
    }
}
 
void DFS(int a){
    LIT it;
    Renum[a] = C;
    SZ[C] = SZ[C] + P[a];
    for (it = E[a].begin(); it != E[a].end(); it++){
        if (!(it->ck) && !Renum[it->b]){
            DFS(it->b);
        }
    }
}
 
void Make_Compress(){
    int i, x, y;
    for (i = 1; i <= N; i++){
        if (!Renum[i]){
            C++;
            DFS(i);
        }
    }
    for (i = 1; i <= N; i++)E[i].clear();
    for (i = 0; i < cnt; i++){
        x = Renum[def_E[i].a], y = Renum[def_E[i].b];
        tp.a = x, tp.b = y, tp.ck = false, tp.gap = def_E[i].gap;
        E[x].push_back(tp);
        tp.a = y, tp.b = x;
        E[y].push_back(tp);
    }
    N = C;
}
 
long long DP[30], Sum;
 
void DFS2(int a){
    DP[a] += SZ[a];
    LIT it;
    for (it = E[a].begin(); it != E[a].end(); it++){
        if (DP[it->b])continue;
        DFS2(it->b);
        if (it->ck){
            Sum += DP[it->b] * (long long)it->gap;
        }
        DP[a] += DP[it->b];
    }
    return;
}
 
long long Calc()
{
    int i;
    for (i = 1; i <= N; i++)DP[i] = 0;
    Sum = 0;
    DFS2(1);
    return Sum;
}
 
void Make_MST(int a, bool ck){
    if (a == K){
        if (!ck) Make_Compress();
        else{
            long long t = Calc();
            if (Res < t)Res = t;
        }
        return;
    }
    if (ck)Make_MST(a + 1, ck);
    int i, x = w[a].a, y = w[a].b, Max = -1, ma, mb, ty, cc=0;
    Edge3 TP[22];
    if (ck)x = Renum[x], y = Renum[y];
    ty = y;
    for (i = 1; i <= N; i++){
        par2[i].a = 0;
    }
    BFS(x);
    while (y != x){
        if (!par2[y].ck && Max < par2[y].gap){
            ma = y, mb = par2[y].a, Max = par2[y].gap;
        }
        y = par2[y].a;
    }
    if (Max == -1){
        Make_MST(a + 1, ck);
        return;
    }
    if(!ck) def_E[cnt].a = ma, def_E[cnt].b = mb, def_E[cnt++].gap = Max;
    Modify(ma, mb, -1);
    Modify(mb, ma, -1);
    y = ty;
    tp.a = x, tp.b = y, tp.gap = Max, tp.ck = true;
    E[x].push_back(tp);
    tp.a = y, tp.b = x;
    E[y].push_back(tp);
    while (y != x){
        if (par2[y].ck && Max < par2[y].gap){
            TP[cc++] = par2[y];
            Modify(y, par2[y].a, Max);
            Modify(par2[y].a, y, Max);
        }
        y = par2[y].a;
    }
    Make_MST(a + 1, ck);
    if (!ck)return;
    y = ty;
    Modify(x, y, -1);
    Modify(y, x, -1);
    tp.a = ma, tp.b = mb, tp.gap = Max, tp.ck = false;
    E[ma].push_back(tp);
    tp.a = mb, tp.b = ma;
    E[mb].push_back(tp);
    for (i = 0; i < cc; i++){
        Modify(TP[i].a, TP[i].b, TP[i].gap);
        Modify(TP[i].b, TP[i].a, TP[i].gap);
    }
}
int main()
{
    int i;
    scanf("%d%d%d", &N, &M, &K);
    for (i = 0; i < M; i++){
        scanf("%d%d%d", &Ed[i].a, &Ed[i].b, &Ed[i].c);
    }
    sort(Ed, Ed + M);
    for (i = 0; i < K; i++){
        scanf("%d%d", &w[i].a, &w[i].b);
    }
    for (i = 1; i <= N; i++){
        scanf("%d", &P[i]);
    }
    init();
    Make_MST(0, 0);
    Make_MST(0, 1);
    printf("%lld\n", Res);
    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:195: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:197:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &Ed[i].a, &Ed[i].b, &Ed[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:201:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &w[i].a, &w[i].b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:204:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &P[i]);
         ~~~~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 5 ms 2644 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 2644 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
3 Correct 7 ms 2792 KB Output is correct
4 Correct 6 ms 2792 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 2644 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
3 Correct 7 ms 2792 KB Output is correct
4 Correct 6 ms 2792 KB Output is correct
5 Correct 12 ms 2976 KB Output is correct
6 Correct 12 ms 3052 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 2644 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
3 Correct 7 ms 2792 KB Output is correct
4 Correct 6 ms 2792 KB Output is correct
5 Correct 12 ms 2976 KB Output is correct
6 Correct 12 ms 3052 KB Output is correct
7 Correct 954 ms 19104 KB Output is correct
8 Correct 904 ms 19104 KB Output is correct
9 Correct 873 ms 19156 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 2644 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
3 Correct 7 ms 2792 KB Output is correct
4 Correct 6 ms 2792 KB Output is correct
5 Correct 12 ms 2976 KB Output is correct
6 Correct 12 ms 3052 KB Output is correct
7 Correct 954 ms 19104 KB Output is correct
8 Correct 904 ms 19104 KB Output is correct
9 Correct 873 ms 19156 KB Output is correct
10 Correct 1819 ms 19156 KB Output is correct
11 Correct 2176 ms 19172 KB Output is correct
12 Correct 2330 ms 19180 KB Output is correct