oj.uz

Submission #51901

# Submission time Handle Problem Language Result Execution time Memory
51901 2018-06-22T14:02:51 Z someone_aa timeismoney (balkan11_timeismoney) C++17
65 / 100
 2000 ms 1276 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 += 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
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 792 KB Output is correct
4 Correct 2 ms 792 KB Output is correct
5 Correct 7 ms 840 KB Output is correct
6 Correct 4 ms 840 KB Output is correct
7 Correct 76 ms 896 KB Output is correct
8 Correct 1927 ms 1148 KB Output is correct
9 Correct 2 ms 1148 KB Output is correct
10 Correct 2 ms 1148 KB Output is correct
11 Incorrect 2 ms 1148 KB Output isn't correct
12 Correct 2 ms 1148 KB Output is correct
13 Correct 2 ms 1148 KB Output is correct
14 Incorrect 5 ms 1148 KB Output isn't correct
15 Correct 3 ms 1148 KB Output is correct
16 Incorrect 96 ms 1148 KB Output isn't correct
17 Incorrect 72 ms 1148 KB Output isn't correct
18 Incorrect 75 ms 1148 KB Output isn't correct
19 Execution timed out 2029 ms 1180 KB Time limit exceeded
20 Incorrect 1971 ms 1276 KB Output isn't correct