oj.uz

답안 #580977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580977 2022-06-22T07:21:17 Z 반딧불(#8360) 통행료 (APIO13_toll) C++17
16 / 100
 206 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct unionFind{
    int par[12];

    void init(int _n){
        for(int i=0; i<=_n; i++) par[i]=i;
    }

    int find(int x){
        if(x==par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
} dsu;

struct Edge{
    int x, y; ll z;
    Edge(int x, int y, ll z): x(x), y(y), z(z){}

    bool operator<(const Edge &r)const{
        return z>r.z;
    }
};

int n, m, k;
int s, e;
int x[22], y[22];
ll z[22];
ll arr[12];
ll ans;

vector<pair<int, ll> > link[12];

ll calc(){
    priority_queue<Edge> pq;
    for(int i=1; i<=m+1; i++) pq.push(Edge(x[i], y[i], z[i]));
    dsu.init(n);
    ll ret = 0;
    while(!pq.empty()){
        Edge tmp = pq.top(); pq.pop();
        if(dsu.find(tmp.x) == dsu.find(tmp.y)) continue;
        ret += tmp.z;
        dsu.merge(tmp.x, tmp.y);
    }
    return ret;
}

vector<int> link2[12];

ll dfs(int x, int p=-1, bool now=0){
    ll ret = arr[x] * now;
    for(auto y: link2[x]){
        if(y==p) continue;
        ret += dfs(y, x, (x+y==s+e&&x*y==s*e) ? 1 : now);
    }
    return ret;
}

ll getAns(int d, ll S){
    for(int i=1; i<=n; i++) link2[i].clear();
    dsu.init(n);
    for(int i=1; i<=m; i++){
        if(d&(1<<(i-1))){
            link2[x[i]].push_back(y[i]), link2[y[i]].push_back(x[i]);
            dsu.merge(x[i], y[i]);
        }
    }
    link2[s].push_back(e);
    link2[e].push_back(s);
    dsu.merge(s, e);

    for(int i=2; i<=n; i++) if(dsu.find(1) != dsu.find(i)) return -1;
    return dfs(1)*S;
}

int main(){
    scanf("%d %d %d", &n, &m, &k);
    vector<ll> vec;
    for(int i=1; i<=m; i++){
        scanf("%d %d %lld", &x[i], &y[i], &z[i]);
        vec.push_back(z[i]);
    }
    scanf("%d %d", &s, &e);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);

    for(auto S: vec){
        for(int i=1; i<=n; i++) link[i].clear();
        x[m+1] = s, y[m+1] = e, z[m+1] = S;
        for(int i=1; i<=m+1; i++){
            link[x[i]].push_back(make_pair(y[i], z[i]));
            link[y[i]].push_back(make_pair(x[i], z[i]));
        }
        ll minWeight = calc();
        for(int d=0; d<(1<<m); d++){
            if(__builtin_popcount(d) != n-2) continue;
            ll sum = 0;
            for(int j=1; j<=m; j++) if(d&(1<<(j-1))) sum+=z[j];
            if(sum+S!=minWeight) continue;
            ans = max(ans, getAns(d, S));
        }
    }
    printf("%lld", ans);
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%d %d %lld", &x[i], &y[i], &z[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d %d", &s, &e);
      |     ~~~~~^~~~~~~~~~~~~~~~~
toll.cpp:93:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 280 KB Output is correct
2 Correct 104 ms 276 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 280 KB Output is correct
2 Correct 104 ms 276 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 280 KB Output is correct
2 Correct 104 ms 276 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 280 KB Output is correct
2 Correct 104 ms 276 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 280 KB Output is correct
2 Correct 104 ms 276 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -