oj.uz

Submission #51861

# Submission time Handle Problem Language Result Execution time Memory
51861 2018-06-22T07:54:08 Z someone_aa timeismoney (balkan11_timeismoney) C++17
65 / 100
 583 ms 1388 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxe = 10100;
const int maxn = 210;
ll st[maxe], fh[maxe], ti[maxe], co[maxe];
ll edgevalue[maxe], n, m, value[maxe];
bool criticaledge[maxe];
bool edge[maxn][maxn];
bool visited[maxn];
bool deleted[maxe];
vector<int>g[maxn];

void dfs(int node) {
    if(visited[node]) return;
    visited[node] = true;

    for(int u:g[node]) {
        if(!visited[u] && edge[node][u]) {
            dfs(u);
        }
    }
}

bool iscritical(int ind) {
    if(criticaledge[ind]) return true;
    edge[st[ind]][fh[ind]] = edge[fh[ind]][st[ind]] = false;
    memset(visited,false,sizeof(visited));
    dfs(1);
    edge[st[ind]][fh[ind]] = edge[fh[ind]][st[ind]] = true;
    int br = 0;
    for(int i=0;i<n;i++)
        if(visited[i]) br++;

    if(br == n) {
        criticaledge[ind] = false;
        return false;
    }
    else return criticaledge[ind] = true;
}

int main() {
    cin>>n>>m;
    ll u, v, t, c;
    ll sumtime = 0LL;
    ll sumcost = 0LL;
    for(int i=0;i<m;i++) {
        cin>>u>>v>>t>>c;
        st[i] = u; fh[i] = v;
        ti[i] = t; co[i] = c;
        g[u].pb(v);
        g[v].pb(u);
        edge[u][v] = edge[v][u] = true;
        sumtime += ti[i];
        sumcost += co[i];
    }

    int edgecnt = m;
    while(edgecnt > n-1) {
        ll maxvalue = 0LL, maxind = 0;
        for(int i=0;i<m;i++) {
            value[i] = (1LL*ti[i]*sumcost)+(1LL*co[i]*sumtime);
            if(!criticaledge[i]) {
                if(value[i] > maxvalue) {
                    maxvalue = value[i];
                    maxind = i;
                }
            }
        }
        while(iscritical(maxind)) {
            maxvalue = 0LL;
            maxind = 0;
            for(int i=0;i<m;i++) {
                if(!criticaledge[i] && value[i] != 0) {
                    if(value[i] > maxvalue) {
                        maxvalue = value[i];
                        maxind = i;
                    }
                }
            }
        }
        edge[st[maxind]][fh[maxind]]=edge[fh[maxind]][st[maxind]]=false;
        sumcost -= co[maxind];
        sumtime -= ti[maxind];
        co[maxind] = 0;
        ti[maxind] = 0;
        edgecnt--;
    }
    cout<<sumtime<<" "<<sumcost<<"\n";
    for(int i=0;i<m;i++) {
        if(edge[st[i]][fh[i]]) cout<<st[i]<<" "<<fh[i]<<"\n";
    }
    return 0;
}

Subtask #1
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 4 ms 572 KB Output is correct
6 Correct 3 ms 572 KB Output is correct
7 Correct 35 ms 752 KB Output is correct
8 Correct 512 ms 1116 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Incorrect 2 ms 1116 KB Output isn't correct
12 Correct 2 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Incorrect 4 ms 1116 KB Output isn't correct
15 Correct 3 ms 1116 KB Output is correct
16 Incorrect 35 ms 1116 KB Output isn't correct
17 Incorrect 37 ms 1116 KB Output isn't correct
18 Incorrect 35 ms 1116 KB Output isn't correct
19 Incorrect 526 ms 1260 KB Output isn't correct
20 Incorrect 583 ms 1388 KB Output isn't correct