oj.uz

Submission #51900

# Submission time Handle Problem Language Result Execution time Memory
51900 2018-06-22T14:02:11 Z someone_aa timeismoney (balkan11_timeismoney) C++17
60 / 100
 2000 ms 1384 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define mp make_pair
using namespace std;
const int maxn = 210;
const int maxedges = 10100;
int edge[maxn][maxn];
bool bridge[maxedges];
ll cost[maxedges], t[maxedges], n, m;
int s[maxedges], f[maxedges];
ll sumcost, sumtime;
bool visited[maxn];
bool deleted[maxedges];
ll value[maxedges];
vector<int> g[maxn];
int tin[maxn], fup[maxn];
int timer;

void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = fup[v] = timer++;
    for (int to : g[v]) {
        if(edge[to][v] != -1) {
            if (to == p) continue;
            if (visited[to]) {
                fup[v] = min(fup[v], tin[to]);
            } else {
                dfs(to, v);
                fup[v] = min(fup[v], fup[to]);
                if (fup[to] > tin[v]) {
                    bridge[edge[to][v]]=true;
                }
            }
        }
    }
}

void find_bridges() {
    timer = 0;
    memset(visited,false,sizeof(visited));
    memset(tin, -1, sizeof(tin));
    memset(fup, -1, sizeof(fup));
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
}

int main() {
    cin>>n>>m;
    memset(edge,-1,sizeof(edge));
    for(int i=0;i<m;i++) {
        cin>>s[i]>>f[i]>>t[i]>>cost[i];
        sumcost += 1LL * cost[i]; sumtime += 1LL * t[i];
        edge[s[i]][f[i]] = edge[f[i]][s[i]] = i;
        g[s[i]].pb(f[i]);
        g[f[i]].pb(s[i]);
    }

    int edges = m;
    while(edges > n-1) {
        find_bridges();

        ll maxvalue = 0LL;
        ll maxind = -1;
        for(int i=0;i<m;i++) {
            if(!deleted[i] && !bridge[i]) {
                value[i] = (1LL*cost[i] * sumtime) + (1LL*t[i]*sumcost);

                if(value[i] > maxvalue) {
                    maxvalue = value[i];
                    maxind = i;
                }
            }
        }

        deleted[maxind] = true;
        edge[s[maxind]][f[maxind]] = edge[f[maxind]][s[maxind]] = -1;
        sumcost -= cost[maxind];
        sumtime -= t[maxind];
        cost[maxind] = 0;
        t[maxind] = 0;
        edges--;
    }
    cout<<sumtime<<" "<<sumcost<<"\n";
    for(int i=0;i<m;i++) {
        if(!deleted[i]) {
            cout<<s[i]<<" "<<f[i]<<"\n";
        }
    }
    return 0;
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 2 ms 664 KB Output is correct
4 Correct 2 ms 664 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 84 ms 928 KB Output is correct
8 Execution timed out 2015 ms 1372 KB Time limit exceeded
9 Correct 3 ms 1372 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Incorrect 2 ms 1372 KB Output isn't correct
12 Correct 4 ms 1372 KB Output is correct
13 Correct 3 ms 1372 KB Output is correct
14 Incorrect 5 ms 1372 KB Output isn't correct
15 Correct 5 ms 1372 KB Output is correct
16 Incorrect 99 ms 1372 KB Output isn't correct
17 Incorrect 91 ms 1372 KB Output isn't correct
18 Incorrect 76 ms 1372 KB Output isn't correct
19 Incorrect 1998 ms 1372 KB Output isn't correct
20 Execution timed out 2058 ms 1384 KB Time limit exceeded