Submission #247102

#	Time	Username	Problem	Language	Result	Execution time	Memory
247102		sealnot123	Toll (APIO13_toll)	C++14	56 / 100	160 ms	10676 KiB

toll

#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())
#define mt make_tuple

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 = 1005, K = 15;
LL people[N];
int mark[N+K], ans[N+K];
vector< tuple<int,int,int> > g[N], edge;
queue<int> bfs;
bool visit[N];
int level[N], wp[N], parent[N];
int n;
bool iterate(int total, int &CH){
    memset(visit, 0, sizeof visit);
    memset(parent, 0, sizeof parent);
    memset(level, 0, sizeof level);
    visit[1] = true;
    bfs.push(1);
    while(!bfs.empty()){
        int u = bfs.front();
        bfs.pop();
        for(auto &e : g[u]){
            int a, b ,c; // node, weight, address
            tie(a, b, c) = e;
            if(mark[c] == -1) continue;
            if(parent[u] == a) continue;
            if(visit[a]){
                mark[c] = 0; continue;
            }
            visit[a] = true;
            level[a] = level[u]+1;
            parent[a] = u;
            wp[a] = c;
            mark[c] = 1;
            bfs.push(a);
        }
    }
    int cnt = 0;
    FOR(i, 0, total-1){
            int a, b, c; // node1, node2, weight
            tie(a, b, c) = edge[i];
        if(mark[i] != 0) continue;
        ++cnt;
            // find max
            int Max = c, x;
            int aa = a, bb = b;
            while(a != b){
                if(level[a] < level[b]) swap(a,b);
                if((x = get<2>(edge[wp[a]])) > 0){
                    Max = max(Max, x);
                }
                a = parent[a];
            }
            if(Max == -1){
                CH = 0; return false;
            }
            ans[i] = min(ans[i], Max);
            if(c == Max){
                mark[i] = -1;
            }
            a = aa; b = bb;
            while(a != b){
                if(level[a] < level[b]) swap(a,b);
                int x = get<2>(edge[wp[a]]);
                int &y = ans[wp[a]];
                y = min(y, Max);
                if(x == Max) mark[wp[a]] = -1;
                a = parent[a];
            }
    }
    //printf("ans :"); FOR(i, 0, total-1) printf("%d ",ans[i]);
    //puts("");
    //printf("wp :"); FOR(i, 1, n) printf("%d ",wp[i]);
    //puts("");
    if(cnt != 0 ) return true;
    return false;
}
LL dfs(int u, int p, LL &value){
    LL sz = people[u];
    for(auto &e : g[u]){
        int a, b, c;
        tie(a,b,c) = e;
        if(a == p) continue;
        if(mark[c] == -1) continue;
        sz += dfs(a, u, value);
    }
    if(u != 1){
        int a, b, c;
        tie(a,b,c) = edge[wp[u]];
        if(c == -1) value += sz * ans[wp[u]];
    }
    return sz;
}
LL play(int total){
    memset(mark, 0, sizeof mark);
    FOR(i, 1, n) g[i].clear();
    FOR(i, 0, total-1) ans[i] = 1<<30;
    FOR(i, 0, total-1){
        int a, b, c;
        tie(a, b, c) = edge[i];
        //printf("Add edge : (%d,%d)\n",a,b);
        g[a].pb(mt(b,c,i));
        g[b].pb(mt(a,c,i));
    }
    int ch = 1;
    while(iterate(total, ch));
    if(ch == 0) return -1;
    LL value = 0;
    dfs(1,1,value);
    return value;
}

int p[N];
int fin(int i){
    if(i == p[i]) return i;
    return p[i]=fin(p[i]);
}
vector<pair<int,PII>> edge_init;
vector<tuple<int,int,int>> edge_mst, edge_k;
int main(){
    int m, k;
    scanf("%d %d %d",&n,&m,&k);
    FOR(i, 1, m){
        int a, b, c;
        scanf("%d %d %d",&a,&b,&c);
        edge_init.pb( {c, PII(a, b)} );
    }
    sort(all(edge_init));
    FOR(i, 1, n) p[i] = i;
    for(auto &e : edge_init){
        int a, b;
        a = e.y.x; b = e.y.y;
        if(fin(a) != fin(b)){
            edge_mst.pb(mt(a, b, e.x));
            //printf("(%d, %d) selected\n",a,b);
            p[fin(a)] = fin(b);
        }
    }
    FOR(i, 1, k){
        int a, b;
        scanf("%d %d",&a,&b);
        edge_k.pb(mt(a, b, -1));
    }
    FOR(i, 1, n) scanf("%lld",&people[i]);
    LL answer = 0;
    FOR(i, 1, (1<<k)-1){
        edge.clear();
        edge = edge_mst;
        FOR(j, 0, k-1){
            if(i & (1<<j)){
                edge.pb( edge_k[j] );
            }
        }
        answer = max(answer, play(SZ(edge)));
    }
    printf("%lld",answer);
	return 0;
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
 */

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:141: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:144: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:160: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:163:23: 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 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22