Submission #73930

#	Time	Username	Problem	Language	Result	Execution time	Memory
73930		ainta	Toll (APIO13_toll)	C++17	100 / 100	2330 ms	19180 KiB

toll

#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 (stderr)

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]);
         ~~~~~^~~~~~~~~~~~~

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