Submission #1150959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150959		arshjeet	Toll (APIO13_toll)	C++20	16 / 100	2 ms	4936 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int N = 1e5+1;
const int INF = 1e6;
set<vector<int>> edges; // wt, v1, v2
vector<pair<int,int>> g[N];
vector<pair<int,int>> mst[N];
int sz[N];
int parent[N];
int level[N];
int bfsvis[N];
int ppl[N];

int dfs(int v, int p){
    int ans=ppl[v];
    for(auto node : mst[v]){
        int child = node.first;
        if(child==p) continue;
        ans+=dfs(child,v);
    }
    return ans;
}

void bfs(int src){
    queue<int> q;
    level[src]=0;
    bfsvis[src]=1;
    q.push(src);

    while(q.size()>0){
        int v = q.front();
        q.pop();
        bfsvis[v]=1;
        for(auto node : mst[v]){
            int child = node.first;
            if(bfsvis[child]) continue;
            q.push(child);
            level[child] = level[v]+1;
        } 
    }
}

bool roadexists(int v1, int v2){
    for(auto child : mst[v1]){
        int v = child.first;
        if(v==v2) return true;
    }
    return false;
}

//***********U F D S*********************
void make(int a){
    parent[a]=a;
    sz[a]=1;
}

int find(int v){
    if(v==parent[v]){
        return v;
    }
    parent[v]=find(parent[v]);
    return parent[v];
}

void Union(int a, int b){
    a=find(a);
    b=find(b);

    if(a!=b){
        if(sz[a]<sz[b]){
            swap(a,b);
        }
        parent[b]=a;
        sz[a]+=sz[b];
    }
}
//**************************8

void kruskal(int n){
    for(int i=1;i<=n;++i) make(i);
    for(int i=1;i<=n;++i){
        mst[i].clear();
    }    

    for(auto edge : edges){

        int wt = edge[0];
        int v1 = edge[1];
        int v2 = edge[2];

        if(find(v1)==find(v2)) continue;
        Union(v1,v2);
        mst[v1].pb({v2,wt});
        mst[v2].pb({v1,wt});
    }
}

signed main() {
    fast();
    int n,m,k; cin>>n>>m>>k;
    map<pair<int,int>,int> dist;
    //*************input******************

    for(int i=0;i<m;++i){
        int a,b,c; cin>>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
        edges.insert({c,a,b});
    }
    vector<pair<int,int>> newroads;
    for(int i=0;i<k;++i){
        int x,y; cin>>x>>y;
        newroads.pb({x,y});
        edges.insert({INF,x,y});
        dist[{x,y}] = INF;
        dist[{y,x}] = INF;
    }

    for(int i=1;i<=n;++i){
        cin>>ppl[i];
    }

    //*************************************

    for(int i=0;i<k;++i){
        int v1 = newroads[i].first;
        int v2 = newroads[i].second;

        int lo = 1;
        int hi = INF;

        //BINARY SEARCH TO FIND MAX FEE ST ROAD IS INCLUDED IN MST***********

        while(hi-lo>1){
            int mid = (hi+lo)/2;

            if(edges.find({dist[{v1,v2}] , v1, v2}) != edges.end()){
                edges.erase({dist[{v1,v2}] , v1, v2});
            }
            else{
                edges.erase({dist[{v1,v2}] , v2, v1});
            }
            edges.insert({mid, v1, v2});
            dist[{v1,v2}] = mid;
            dist[{v2,v1}] = mid;

            kruskal(n);

            if(roadexists(v1,v2)){
                lo=mid;
            }
            else{
                hi=mid-1;
            }
        }

        if(edges.find({dist[{v1,v2}] , v1, v2}) != edges.end()){
                edges.erase({dist[{v1,v2}] , v1, v2});
        }
        else{
            edges.erase({dist[{v1,v2}] , v2, v1});
        }
        edges.insert({hi, v1, v2});
        dist[{v1,v2}] = hi;
        dist[{v2,v1}] = hi;
        kruskal(n);

        if(!roadexists(v1,v2)){
            edges.erase({hi,v1,v2});
            edges.insert({lo,v1,v2});
            dist[{v1,v2}]=lo;
            dist[{v2,v1}]=lo;
            kruskal(n);            
        }

        //*****************************************
    }


    //FINAL MST IS NOW READY
    //bfs on 1 to find which of the cities at endpts of
    //the k roads are furhter apart from 1

    
    bfs(1);
    int ans = 0;
    for (auto it = dist.begin(); it != dist.end(); ++it) {
        auto pr = it->first;
        int v1 = pr.first;
        int v2 = pr.second;

        // Ensure v2 is farther from town 1 than v1
        if (level[v1] > level[v2]) continue;

        // Count participants passing through the new road
        int z = dfs(v2, v1);
        //cout<<dfs(v2,v1)<<" "<<v2<<" "<<v1<<"\n";
        ans += z * dist[{v1, v2}];
    }

    cout << ans;
    
    /*
    for(int i=1;i<=n;++i){
        for(auto node : mst[i]){
            cout << "city "<<i<<" is connected with city "<<node.first<<" and has fee "<<node.second<<"\n";
        }
    }
    */
    
}

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