oj.uz

Submission #51899

# Submission time Handle Problem Language Result Execution time Memory
51899 2018-06-22T14:00:46 Z someone_aa timeismoney (balkan11_timeismoney) C++17
65 / 100
 1943 ms 1248 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];
int 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 += cost[i]; sumtime += 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
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 2 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 4 ms 752 KB Output is correct
7 Correct 78 ms 868 KB Output is correct
8 Correct 1943 ms 1248 KB Output is correct
9 Correct 3 ms 1248 KB Output is correct
10 Correct 3 ms 1248 KB Output is correct
11 Incorrect 3 ms 1248 KB Output isn't correct
12 Correct 3 ms 1248 KB Output is correct
13 Correct 2 ms 1248 KB Output is correct
14 Incorrect 6 ms 1248 KB Output isn't correct
15 Correct 4 ms 1248 KB Output is correct
16 Incorrect 73 ms 1248 KB Output isn't correct
17 Incorrect 72 ms 1248 KB Output isn't correct
18 Incorrect 71 ms 1248 KB Output isn't correct
19 Incorrect 1891 ms 1248 KB Output isn't correct
20 Incorrect 1892 ms 1248 KB Output isn't correct