oj.uz

Submission #581077

# Submission time Handle Problem Language Result Execution time Memory
581077 2022-06-22T09:01:17 Z 반딧불(#8360) Toll (APIO13_toll) C++17
16 / 100
 19 ms 416 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct unionFind{
    int par[1002];

    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[1002];
bool isNew[1002][1002];
Edge edge[5002];
int ex[22], ey[22];
ll arr[1002];
ll ans;

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

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 + (isNew[x][y.first] ? 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]);
        isNew[ex[i]][ey[i]] = 1;
        isNew[ey[i]][ex[i]] = 1;
    }
    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;
        vector<int> oneOfMarked;
        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]);
            oneOfMarked.push_back(ex[i]);
            oneOfMarked.push_back(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;

        sort(oneOfMarked.begin(), oneOfMarked.end());
        oneOfMarked.erase(unique(oneOfMarked.begin(), oneOfMarked.end()), oneOfMarked.end());

        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){
                    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

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 22.0

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