Submission #51899

#	Time	Username	Problem	Language	Result	Execution time	Memory
51899		someone_aa	timeismoney (balkan11_timeismoney)	C++17	65 / 100	1943 ms	1248 KiB

timeismoney

#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 / 100