oj.uz

Submission #683092

# Submission time Handle Problem Language Result Execution time Memory
683092 2023-01-17T16:29:41 Z vjudge1 timeismoney (balkan11_timeismoney) C++17
100 / 100
 961 ms 1100 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
#define ff first
#define ss second
const int maxn = 10010;
int n,m;
iii res;
ii e[maxn];
int t[maxn],c[maxn],w[maxn];
int p[maxn],s[maxn],id[maxn],vis[maxn];
int get(int x)
{
    return p[x]=(p[x]==x)?x:get(p[x]);
}
bool hop(int x, int y)
{
    x=get(x); y=get(y);
    if (x==y) return 0;
    if (s[x]>s[y]) swap(x,y);
    s[y]+=s[x];
    p[x]=y;
    return 1;
}
bool cmp(int x, int y)
{
    return w[x]<w[y];
}
ii mst(int A, int B)
{
    for (int i=1; i<=m; i++)
    {
        w[i]=A*t[i] + B*c[i];
        id[i]=i;
        vis[i]=0;
    }
//    for (int i=1; i<=m; i++) cout<<w[i]<<' '; cout<<'\n';
    sort(id+1,id+m+1,cmp);
//    for (int i=1; i<=m; i++) cout<<w[i]<<' '; cout<<'\n';
    for (int i=1; i<=n; i++) p[i]=i,s[i]=1;
    ii ans={0,0};
    for (int j=1; j<=m; j++)
    {
        int i=id[j];
        if (hop(e[i].ff,e[i].ss))
        {
            vis[i]=1;
            ans.ff+=t[i];
            ans.ss+=c[i];
        }
    }
    return ans;
}

void dnc(ii x, ii y)
{
    if (x==y) return;
    ii z = mst(x.ss-y.ss,y.ff-x.ff);
//    cout<<z.ff<<' '<<z.ss<<' '<<x.ss-y.ss<<" "<<y.ff-x.ff<<'\n';
    res=min(res,{z.ff*z.ss,{x.ss-y.ss,y.ff-x.ff}});
    if (x==z||y==z) return;
    dnc(x,z); dnc(z,y);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        int u,v; cin>>u>>v>>t[i]>>c[i];
        u++; v++;
        e[i]={u,v};
    }
//    cout<<"----------\n";
    ii i = mst(1,0); ii j = mst(0,1);
    res={i.ff*i.ss,{1,0}};
    res=min(res,{j.ff*j.ss,{0,1}});
//    cout<<i.ff<<' '<<i.ss<<" : "<<j.ff<<' '<<j.ss<<'\n';
    dnc(i,j);
    ii ans = mst(res.ss.ff,res.ss.ss);
    cout<<ans.ff<<' '<<ans.ss<<'\n';
    for (int i=1; i<=m; i++)
        if (vis[i]) cout<<e[i].ff-1<<' '<<e[i].ss-1<<'\n';
}/**
5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92
**/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 6 ms 980 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 6 ms 332 KB Output is correct
15 Correct 4 ms 340 KB Output is correct
16 Correct 101 ms 468 KB Output is correct
17 Correct 109 ms 480 KB Output is correct
18 Correct 100 ms 468 KB Output is correct
19 Correct 947 ms 1000 KB Output is correct
20 Correct 961 ms 1100 KB Output is correct