Submission #581324

#	Time	Username	Problem	Language	Result	Execution time	Memory
581324		79brue	Toll (APIO13_toll)	C++17	78 / 100	2582 ms	12580 KiB

toll

#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;
unordered_set<ll> st;
Edge edge[500002];
int ex[22], ey[22];
int root;
ll arr[100002];
ll ans;

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

void input(){
    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);
    }
    sort(edge+1, edge+m+1);
    for(int i=0; i<k; i++){
        scanf("%d %d", &ex[i], &ey[i]);
    }
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
}


vector<int> specialVec (1, -1);
int indices[100002];
int group[100002];
ll minWeight[42][42];

void contractGraph(){
    dsu.init(n);
    dsu2.init(n);
    for(int i=0; i<k; i++){
        dsu.merge(ex[i], ey[i]);
        specialVec.push_back(ex[i]);
        specialVec.push_back(ey[i]);
    }
    sort(specialVec.begin(), specialVec.end());
    specialVec.erase(unique(specialVec.begin(), specialVec.end()), specialVec.end());
    for(int i=1; i<(int)specialVec.size(); i++) indices[specialVec[i]] = i;

    for(int i=1; i<=m; i++){
        Edge e = edge[i];
        if(dsu.find(e.x) == dsu.find(e.y)) continue;
        dsu.merge(e.x, e.y);
        dsu2.merge(e.x, e.y);
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<(int)specialVec.size(); j++){
            if(dsu2.find(i) == dsu2.find(specialVec[j])){
                group[i] = j;
                break;
            }
        }
        assert(group[i]);
    }
    root = group[1];

    vector<ll> tarr (arr, arr+n+1);
    memset(arr, 0, sizeof(arr));
    for(int i=1; i<=n; i++) arr[group[i]] += tarr[i];
    n = (int)specialVec.size()-1;
    assert(n<=k*2);

    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) minWeight[i][j] = 1e18;
    vector<Edge> edgeVec;
    for(int i=1; i<=m; i++){
        edge[i].x = group[edge[i].x], edge[i].y = group[edge[i].y];
        if(edge[i].x == edge[i].y) continue;
        if(edge[i].x > edge[i].y) swap(edge[i].x, edge[i].y);
        minWeight[edge[i].x][edge[i].y] = min(minWeight[edge[i].x][edge[i].y], edge[i].z);
//        edgeVec.push_back(Edge(edge[i].x, edge[i].y, edge[i].z));
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        if(minWeight[i][j] > 1e17) continue;
        edgeVec.push_back(Edge(i, j, minWeight[i][j]));
    }
    sort(edgeVec.begin(), edgeVec.end());
    m = (int)edgeVec.size();
    for(int i=1; i<=m; i++){
        edge[i] = edgeVec[i-1];
    }

    for(int i=0; i<k; i++){
        ex[i] = group[ex[i]], ey[i] = group[ey[i]];
        assert(ex[i] != ey[i]);
        st.insert(ll(ex[i])*1000000+ey[i]);
        st.insert(ll(ey[i])*1000000+ex[i]);
    }
}

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(){
    input();
    contractGraph();

    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(int pnt=1; pnt<=m; pnt++){ /// 가장 가중치 작은 edge부터 시도해 보기
            Edge e = edge[pnt];
            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(root));
    }
    printf("%lld", ans);
}

Compilation message (stderr)

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

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 0 / 22