oj.uz

Submission #402570

# Submission time Handle Problem Language Result Execution time Memory
402570 2021-05-12T00:51:53 Z SirCovidThe19th timeismoney (balkan11_timeismoney) C++14
35 / 100
 18 ms 608 KB 
#include <bits/stdc++.h>
using namespace std;

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

int n, m;
vector<store> edges;

int currVal, 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 ansT*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;
    
    int low = 0, high = (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
35.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 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 Incorrect 3 ms 204 KB Output isn't correct
7 Incorrect 3 ms 332 KB Output isn't correct
8 Incorrect 12 ms 608 KB Output isn't 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 2 ms 296 KB Output isn't correct
14 Incorrect 3 ms 204 KB Output isn't correct
15 Incorrect 2 ms 204 KB Output isn't correct
16 Incorrect 4 ms 304 KB Output isn't correct
17 Incorrect 4 ms 304 KB Output isn't correct
18 Incorrect 4 ms 324 KB Output isn't correct
19 Incorrect 15 ms 588 KB Output isn't correct
20 Incorrect 18 ms 560 KB Output isn't correct