oj.uz

Submission #206120

# Submission time Handle Problem Language Result Execution time Memory
206120 2020-03-02T10:20:40 Z gratus907 timeismoney (balkan11_timeismoney) C++17
0 / 100
 2000 ms 1268 KB 
#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.999;
    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;
    }
    cerr << (long long)run_with_config(ratio, true) << '\n';
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 504 KB Extra information in the output file
2 Incorrect 7 ms 376 KB Extra information in the output file
3 Incorrect 8 ms 376 KB Extra information in the output file
4 Incorrect 19 ms 376 KB Extra information in the output file
5 Incorrect 88 ms 376 KB Extra information in the output file
6 Incorrect 74 ms 376 KB Extra information in the output file
7 Incorrect 437 ms 504 KB Extra information in the output file
8 Execution timed out 2061 ms 1140 KB Time limit exceeded
9 Incorrect 8 ms 376 KB Extra information in the output file
10 Incorrect 14 ms 376 KB Extra information in the output file
11 Incorrect 10 ms 376 KB Extra information in the output file
12 Incorrect 25 ms 376 KB Extra information in the output file
13 Incorrect 26 ms 376 KB Extra information in the output file
14 Incorrect 138 ms 376 KB Extra information in the output file
15 Incorrect 119 ms 372 KB Extra information in the output file
16 Incorrect 847 ms 608 KB Extra information in the output file
17 Incorrect 876 ms 524 KB Extra information in the output file
18 Incorrect 815 ms 504 KB Extra information in the output file
19 Execution timed out 2076 ms 1140 KB Time limit exceeded
20 Execution timed out 2075 ms 1268 KB Time limit exceeded