Submission #1141824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141824		Aria_lix19	timeismoney (balkan11_timeismoney)	C++20	40 / 100	15 ms	3524 KiB

timeismoney

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define endl '\n'
vector<vector<pair<int, ll>>>graph, creat;
vector<bool>vis;
vector<int>sign;
map<pair<int, int>, bool>eg;
map<pair<int, int>, pair<ll, ll>>as;
vector<pair<ll, pair<int, int>>>price;
vector<pair<int, int>>out;
int num = 0;
ll sum1 = 0, sum2 = 0;
void dfs(int x){
    vis[x] = 1;
    sign[x] = num;
    for(int i = 0; i < creat[x].size() ; i++){
        auto [ind, cost] = creat[x][i];
        if(!vis[ind]){
            sign[ind] = num;
            dfs(ind);
        }
    }
}
void ans(int x){
    vis[x] = 1;
    for(int i = 0; i < creat[x].size(); i++){
        auto [ind, cost] = creat[x][i];
        if(!vis[ind]){
            out.push_back({x, ind});
            sum1 += as[{x, ind}].first;
            sum2 += as[{x, ind}].second;
            ans(ind);
        }
    }
}
int main(){
    int n, m; cin >> n >> m;
    graph.resize(n+1); creat.resize(n+1); vis.resize(n+1, false); sign.resize(n+1);
    for(int i = 0; i < m; i++){
        int u, v, t, c; cin >> u >> v >> t >> c;
        as[{u, v}] = {t, c};
        as[{v, u}] = {t, c};
        graph[u].push_back({v, t*c});
        graph[v].push_back({u, t*c});
    }
    for(int i = 0; i < n; i++){
        pair<int, ll> r = {0, INT_MAX};
        for(int j = 0; j < graph[i].size(); j++){
            auto [x, y] = graph[i][j];
            if(r.second > y){
                r = {x, y};
            }
        }
        creat[i].push_back({r.first, r.second});
        creat[r.first].push_back({i, r.second});
    }
//    for(int i = 0; i < n; i++){
//        for(int j = 0; j < creat[i].size(); j++){
//            cout << i <<  " " << creat[i][j].first << " " << creat[i][j].second << endl;
//        }
//    }
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            num++;
            dfs(i);
        }
    }
    for(int i = 0; i < n ; i++){
        for(int j = 0; j < creat[i].size(); j++){
            auto [ind, cost] = creat[i][j];
            eg[{i, ind}] = 1;
            eg[{ind, i}] = 1;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < graph[i].size(); j++){
            auto [ind, cost] = graph[i][j];
            if(eg[{i, ind}] == 0){
                price.push_back({cost, {i, ind}});
            }
        }
    }
    sort(price.begin(), price.end());
//    for(int i = 0; i < price.size(); i++){
//        cout << price[i].first << " " << price[i].second.first << " " << price[i].second.second << endl;
//    }
    if(num > 1){
        for(int i = 0; i < price.size() ; i++){
            int x = price[i].second.first, y = price[i].second.second;
            ll cost = price[i].first;
            if(sign[x] != sign[y]){
                creat[x].push_back({y, cost});
                creat[y].push_back({x, cost});
                num = sign[x];
                fill(vis.begin(), vis.end(), false);
                dfs(x);
            }
            bool flag = 1;
            for(int i = 0; i < n ; i++){
                if(!vis[i]) flag = 0;
            }
            if(flag) break;
        }
    }
    fill(vis.begin(), vis.end(), false);
    ans(0);
    cout << sum1 << " " << sum2 << endl;
    for(int i = 0; i < out.size(); i++){
        cout << out[i].first << " " << out[i].second << endl;
    }
}
//6 6
//3 2 1 1
//4 1 2 1
//5 0 1 1
//0 1 5 1
//2 0 2 2
//3 4 3 1

• Subtask 1: 40 / 100