oj.uz

Submission #122431

# Submission time Handle Problem Language Result Execution time Memory
122431 2019-06-28T07:59:35 Z 송준혁(#2992) Toll (APIO13_toll) C++14
16 / 100
 6 ms 2688 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, K;
LL C[101010], ans, sum;
int S[30], E[30];
int P[101010];
vector<pii> adj[101010];

struct Data{
    int u, v, w;
    bool operator<(const Data &r)const{
        return w < r.w;
    }
} A[101010];

int Find(int u){
    if (u == P[u]) return u;
    return P[u] = Find(P[u]);
}

bool MakeG(int m){
    for (int i=1; i<=N; i++) P[i] = i, adj[i].clear();
    for (int i=1; i<=M; i++){
        int u = Find(A[i].u), v = Find(A[i].v);
        if (u == v) continue;
        if (u > v) swap(u, v);
        bool tf = false;
        for (int j=1; j<=K; j++){
            if (~m & (1<<(j-1))) continue;
            int nu = Find(S[j]), nv = Find(E[j]);
            if (nu > nv) swap(nu, nv);
            if (nu == u && nv == v){
                if (tf) return false;
                tf = true;
                adj[S[j]].push_back(pii(E[j], A[i].w));
                adj[E[j]].push_back(pii(S[j], A[i].w));
            }
        }
        if (!tf){
            adj[A[i].u].push_back(pii(A[i].v, 0));
            adj[A[i].v].push_back(pii(A[i].u, 0));
        }
        P[u] = v;
    }
    return true;
}

LL dfs(int u, int p){
    LL ret = 0;
    for (pii v : adj[u]){
        if (v.first == p) continue;
        LL t = dfs(v.first, u);
        ret += t;
        sum += t * v.second;
    }
    return ret + C[u];
}

int main(){
    scanf("%d %d %d", &N, &M, &K);
    for (int i=1; i<=M; i++) scanf("%d %d %d", &A[i].u, &A[i].v, &A[i].w);
    for (int i=1; i<=K; i++) scanf("%d %d", &S[i], &E[i]);
    for (int i=1; i<=N; i++) scanf("%lld", &C[i]);
    sort(A+1, A+M+1);
    for (int i=1; i<(1<<K); i++){
        if(MakeG(i)) {
            dfs(1, 0);
            ans = max(ans, sum);
            sum = 0;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:63: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:64:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=M; i++) scanf("%d %d %d", &A[i].u, &A[i].v, &A[i].w);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:65:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=K; i++) scanf("%d %d", &S[i], &E[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:66:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=N; i++) scanf("%lld", &C[i]);
                              ~~~~~^~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Incorrect 6 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Incorrect 6 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Incorrect 6 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Incorrect 6 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -