oj.uz

Submission #402575

# Submission time Handle Problem Language Result Execution time Memory
402575 2021-05-12T01:13:03 Z SirCovidThe19th timeismoney (balkan11_timeismoney) C++14
50 / 100
 95 ms 460 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

struct store{
    int x, y, t, c;
};

int n, m;
vector<store> edges;

ll currVal; int ansT, ansC; vector<pair<int, int>> links;

vector<int> par, sz; 
int find(int node){
    if (node == par[node]) return node;
    return par[node] = find(par[node]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if (sz[a] > sz[b]) swap(a, b);
    par[a] = b; sz[b] += sz[a];
}

bool cmp1(store a, store b){
    return a.t-((long double)currVal/a.c) < b.t-((long double)currVal/b.c);
}
bool cmp2(store a, store b){
    return a.c-((long double)currVal/a.t) < b.c-((long double)currVal/b.t);
}
bool check(int whichCmp){
    if (whichCmp == 1) sort(edges.begin(), edges.end(), cmp1);
    else sort(edges.begin(), edges.end(), cmp2);
    par.resize(n); sz.resize(n, 1); iota(par.begin(), par.end(), 0);
    for (int i = 0; i < n; i++) par[i] = i;
    ansT = 0, ansC = 0, links.clear();

    for (store edge : edges){
        if (find(edge.x) != find(edge.y)){
            merge(edge.x, edge.y);
            ansT += edge.t, ansC += edge.c; links.push_back({edge.x, edge.y});
        }
    }

    return (ll)ansT*(ll)ansC <= currVal;
}
int main(){
    
    cin >> n >> m; edges.resize(m);
    for (int i = 0; i < m; i++)
        cin >> edges[i].x >> edges[i].y >> edges[i].t >> edges[i].c;

    ll low = 0; ll high = ((ll)255*n*255*n)+1;
    while (low < high){
        currVal = (low+high+1)/2;
        if (check(1) or check(2)){
            high = currVal-1;
        }
        else low = currVal;
    }
    
    cout<<ansT<<" "<<ansC<<endl;
    for (pair<int, int> elem : links) 
        cout<<elem.first<<" "<<elem.second<<endl;
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Correct 11 ms 204 KB Output is correct
8 Correct 45 ms 460 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Incorrect 1 ms 204 KB Output isn't correct
13 Incorrect 1 ms 204 KB Output isn't correct
14 Incorrect 3 ms 204 KB Output isn't correct
15 Incorrect 3 ms 204 KB Output isn't correct
16 Incorrect 23 ms 320 KB Output isn't correct
17 Incorrect 20 ms 320 KB Output isn't correct
18 Incorrect 23 ms 204 KB Output isn't correct
19 Incorrect 95 ms 460 KB Output isn't correct
20 Incorrect 89 ms 440 KB Output isn't correct