oj.uz

Submission #51860

# Submission time Handle Problem Language Result Execution time Memory
51860 2018-06-22T07:49:09 Z someone_aa timeismoney (balkan11_timeismoney) C++17
65 / 100
 620 ms 1904 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]) {
                    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 380 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 656 KB Output is correct
5 Correct 4 ms 656 KB Output is correct
6 Correct 3 ms 740 KB Output is correct
7 Correct 35 ms 924 KB Output is correct
8 Correct 526 ms 1352 KB Output is correct
9 Correct 2 ms 1352 KB Output is correct
10 Correct 2 ms 1352 KB Output is correct
11 Incorrect 2 ms 1352 KB Output isn't correct
12 Correct 3 ms 1352 KB Output is correct
13 Correct 2 ms 1352 KB Output is correct
14 Incorrect 5 ms 1352 KB Output isn't correct
15 Correct 4 ms 1352 KB Output is correct
16 Incorrect 37 ms 1352 KB Output isn't correct
17 Incorrect 38 ms 1352 KB Output isn't correct
18 Incorrect 40 ms 1352 KB Output isn't correct
19 Incorrect 620 ms 1700 KB Output isn't correct
20 Incorrect 593 ms 1904 KB Output isn't correct