oj.uz

Submission #206121

# Submission time Handle Problem Language Result Execution time Memory
206121 2020-03-02T10:21:18 Z gratus907 timeismoney (balkan11_timeismoney) C++17
0 / 100
 543 ms 1012 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.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;
    }
    cerr << (long long)run_with_config(ratio, true) << '\n';
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 376 KB Extra information in the output file
2 Incorrect 5 ms 372 KB Extra information in the output file
3 Incorrect 7 ms 256 KB Extra information in the output file
4 Incorrect 6 ms 376 KB Extra information in the output file
5 Incorrect 14 ms 376 KB Extra information in the output file
6 Incorrect 12 ms 376 KB Extra information in the output file
7 Incorrect 50 ms 376 KB Extra information in the output file
8 Incorrect 222 ms 1000 KB Extra information in the output file
9 Incorrect 5 ms 376 KB Extra information in the output file
10 Incorrect 5 ms 376 KB Extra information in the output file
11 Incorrect 5 ms 256 KB Extra information in the output file
12 Incorrect 7 ms 376 KB Extra information in the output file
13 Incorrect 7 ms 376 KB Extra information in the output file
14 Incorrect 18 ms 376 KB Extra information in the output file
15 Incorrect 17 ms 376 KB Extra information in the output file
16 Incorrect 92 ms 632 KB Extra information in the output file
17 Incorrect 97 ms 376 KB Extra information in the output file
18 Incorrect 87 ms 376 KB Extra information in the output file
19 Incorrect 543 ms 1012 KB Extra information in the output file
20 Incorrect 484 ms 1012 KB Extra information in the output file