Submission #206122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
206122	2020-03-02T10:21:40 Z	gratus907	timeismoney (balkan11_timeismoney)	C++17	100 / 100	552 ms	1016 KB

timeismoney

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#define ll long long
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int ll
using pii = pair<int, int>;
// Original Author : Ashishgup
struct edge
{
    int u, v, t, c;
};
int n, m;
struct Disjoint_Set_Union
{
#define V 202
    int parent[V], size[V];
    Disjoint_Set_Union(int N = V)
    {
        init(N);
    }
    void init(int N)
    {
        for(int i=0;i<N;i++)
        {
            parent[i]=i;
            size[i]=1;
        }
    }
    int Find(int K)
    {
        while(K!=parent[K])
        {
            parent[K]=parent[parent[K]];
            K=parent[K];
        }
        return K;
    }
    int getSize(int K)
    {
        return size[Find(K)];
    }
    void unite(int x, int y)
    {
        int u=Find(x), v=Find(y);
        if(u==v)
            return;
        if(size[u]>size[v])
            swap(u, v);
        size[v]+=size[u];
        size[u] = 0;
        parent[u] = parent[v];
    }
} dsu;
vector <edge> ed;
vector <pii> pt;
inline double run_with_config(double r, bool print = false)
{
    int st = 0, sc = 0;
    int ct = 0;
    dsu.init(n);
    sort(all(ed),[r](edge &a, edge &b)->bool{return a.t+a.c*r<b.t+b.c*r;});


    if (print)
    {
        for (auto it:ed)
        {
            if (dsu.Find(it.u)!=dsu.Find(it.v))
            {
                dsu.unite(it.u, it.v);
                st += it.t;
                sc += it.c;
                ct++;
                pt.push_back({it.u, it.v});
                if (ct == n-1)
                    break;
            }
        }
    }
    else
    {
        for (auto it:ed)
        {
            if (dsu.Find(it.u)!=dsu.Find(it.v))
            {
                dsu.unite(it.u, it.v);
                st += it.t;
                sc += it.c;
                ct++;
                if (ct == n-1)
                    break;
            }
        }
    }
    if (print)
    {
        cout << st << ' ' << sc << '\n';
        for (auto it:pt)
        {
            cout << it.first << ' ' << it.second << '\n';
        }
    }
    return st*sc;
}
int32_t main()
{
    const double magic = 1.5;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(1/magic, magic);
    std::uniform_real_distribution<> dis2(0, 1);
    cin >> n >> m;
    for (int i = 0; i<m; i++)
    {
        int u, v, t, c;
        cin >> u >> v >> t >> c;
        ed.push_back({u,v,t,c});
    }
    double ratio = 1;
    double iT = 1;
    double k = 0.99;
    double e1 = run_with_config(1);
    double e2 = 0;
    while(iT > 0.01)
    {
        double newratio = ratio * dis(gen);
        e2 = run_with_config(newratio);
        double p = exp((e1-e2)/(iT));
        if (p > dis2(gen))
        {
            ratio = newratio;
            e1 = e2;
        }
        iT *= k;
    }
    run_with_config(ratio, true);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	376 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 ms	256 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	14 ms	376 KB	Output is correct
6	Correct	12 ms	376 KB	Output is correct
7	Correct	52 ms	376 KB	Output is correct
8	Correct	236 ms	1016 KB	Output is correct
9	Correct	5 ms	256 KB	Output is correct
10	Correct	6 ms	256 KB	Output is correct
11	Correct	5 ms	256 KB	Output is correct
12	Correct	7 ms	376 KB	Output is correct
13	Correct	7 ms	376 KB	Output is correct
14	Correct	19 ms	376 KB	Output is correct
15	Correct	17 ms	376 KB	Output is correct
16	Correct	94 ms	504 KB	Output is correct
17	Correct	97 ms	376 KB	Output is correct
18	Correct	90 ms	504 KB	Output is correct
19	Correct	552 ms	1012 KB	Output is correct
20	Correct	501 ms	1012 KB	Output is correct