oj.uz

답안 #581095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581095 2022-06-22T09:11:58 Z 반딧불(#8360) 통행료 (APIO13_toll) C++17
56 / 100
 2500 ms 32768 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct unionFind{
    int par[100002];

    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, dsu2;

struct Edge{
    int x, y; ll z;
    Edge(){}
    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;
vector<pair<int, ll> > link[100002];
unordered_set<ll> st;
Edge edge[500002];
int ex[22], ey[22];
ll arr[100002];
ll ans;

vector<pair<int, ll> > rLink[100002];
vector<pair<int, int> > nLink[100002];

ll calc(int x, int p=-1, ll sum=0){
    ll ret = arr[x] * sum;
    for(auto y: rLink[x]){
        if(y.first == p) continue;
        ret += calc(y.first, x, sum + ((st.find(ll(x)*1000000+y.first) != st.end()) ? y.second : 0));
    }
    return ret;
}

bool dfs(int x, int p, int goal, vector<int> &vec){
    if(x==goal) return true;
    for(auto y: nLink[x]){
        if(y.first == p) continue;
        vec.push_back(y.second);
        if(dfs(y.first, x, goal, vec)) return true;
        vec.pop_back();
    }
    for(auto y: rLink[x]){
        if(y.first == p) continue;
        if(dfs(y.first, x, goal, vec)) return true;
    }
    return false;
}

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1; i<=m; i++){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        edge[i] = Edge(x, y, z);
        link[x].push_back(make_pair(y, z));
        link[y].push_back(make_pair(x, z));
    }
    sort(edge+1, edge+m+1);
    for(int i=0; i<k; i++){
        scanf("%d %d", &ex[i], &ey[i]);
        st.insert(ll(ex[i])*1000000+ey[i]);
        st.insert(ll(ey[i])*1000000+ex[i]);
    }
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);

    for(int b=1; b<(1<<k); b++){ /// b: ���õ� �߰� �������� ����
        /// cycle detection
        dsu2.init(n);
        bool bad = 0;
        for(int i=1; i<=n; i++) nLink[i].clear();

        for(int i=0; i<k; i++){
            if((b&(1<<i))==0) continue;
            if(dsu2.find(ex[i]) == dsu2.find(ey[i])){
                bad = 1;
                break;
            }
            dsu2.merge(ex[i], ey[i]);
            nLink[ex[i]].push_back(make_pair(ey[i], i));
            nLink[ey[i]].push_back(make_pair(ex[i], i));
        }
        if(bad) continue;

        dsu.init(n);
        for(int i=1; i<=n; i++) rLink[i].clear();

        for(Edge e: edge){ /// ���� ����ġ ���� edge���� �õ��� ����
            if(dsu.find(e.x) == dsu.find(e.y)) continue;
            ll w = e.z;
            if(dsu2.find(e.x) != dsu2.find(e.y)){ /// �߰��ص� �Ǵ� ���
                rLink[e.x].push_back(make_pair(e.y, w));
                rLink[e.y].push_back(make_pair(e.x, w));
                dsu.merge(e.x, e.y);
                dsu2.merge(e.x, e.y);
            }
            else{ /// �߰��ϸ� �ȵǴ� ���
                vector<int> delVec;
                dfs(e.x, -1, e.y, delVec);
                for(auto x: delVec){
                    nLink[ex[x]].erase(find(nLink[ex[x]].begin(), nLink[ex[x]].end(), make_pair(ey[x], x)));
                    nLink[ey[x]].erase(find(nLink[ey[x]].begin(), nLink[ey[x]].end(), make_pair(ex[x], x)));
                    rLink[ex[x]].push_back(make_pair(ey[x], w));
                    rLink[ey[x]].push_back(make_pair(ex[x], w));
                    dsu.merge(ex[x], ey[x]);
                }
            }
        }

        ans = max(ans, calc(1));
    }
    printf("%lld", ans);
}

Compilation message

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

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7252 KB Output is correct
2 Correct 9 ms 7372 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7252 KB Output is correct
2 Correct 9 ms 7372 KB Output is correct
3 Correct 1652 ms 7360 KB Output is correct
4 Correct 1431 ms 7380 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7252 KB Output is correct
2 Correct 9 ms 7372 KB Output is correct
3 Correct 1652 ms 7360 KB Output is correct
4 Correct 1431 ms 7380 KB Output is correct
5 Correct 2346 ms 7744 KB Output is correct
6 Correct 1045 ms 7740 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7252 KB Output is correct
2 Correct 9 ms 7372 KB Output is correct
3 Correct 1652 ms 7360 KB Output is correct
4 Correct 1431 ms 7380 KB Output is correct
5 Correct 2346 ms 7744 KB Output is correct
6 Correct 1045 ms 7740 KB Output is correct
7 Execution timed out 2586 ms 32768 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7252 KB Output is correct
2 Correct 9 ms 7372 KB Output is correct
3 Correct 1652 ms 7360 KB Output is correct
4 Correct 1431 ms 7380 KB Output is correct
5 Correct 2346 ms 7744 KB Output is correct
6 Correct 1045 ms 7740 KB Output is correct
7 Execution timed out 2586 ms 32768 KB Time limit exceeded
8 Halted 0 ms 0 KB -