oj.uz

Submission #906399

# Submission time Handle Problem Language Result Execution time Memory
906399 2024-01-14T07:44:04 Z MON Graph (BOI20_graph) C++14
58 / 100
 700 ms 24820 KB 
#include<iostream>
#include<random>
#include<ctime>
#include<vector>
#include<bitset>
#include<iomanip>
#include<algorithm>
#pragma GCC optimize("Ofast","fast-math")
using namespace std;
using pii = pair<int,int>;
using pid = pair<int,double>;
const double bulan[] = {0,0.5,-0.5,-1,1,-1.5,1.5,-2,2,2.5,-2.5,3,-3,3.5,-3.5,4,-4,4.5,-4.5,
                        5,-5,5.5,-5.5,6,6.5,-6,-6.5,7,-7,7.5,-7.5};
constexpr double eps = 1e-6;
constexpr int NMAX = 1e5 + 1;

mt19937 rng(time(nullptr));
bitset<NMAX> viz,fix; double ans[NMAX];
vector<pii> vecini[NMAX];

void dfs(int a,vector<int> &u)
{
    u.emplace_back(a); viz[a] = 1;
    for(auto &it : vecini[a])
        if(!viz[it.first]) dfs(it.first,u);
}

void go(int a,double v,vector<pid> &res)
{
    res.push_back({a,v}); viz[a] = 1; ans[a] = v;
    for(auto &it : vecini[a])
        {
            if(!viz[it.first])
                go(it.first,it.second - v,res);
        }
}

long double ab(vector<pid> &h)
{
    long double res = 0;
    for(auto &it : h) res += abs(it.second);
    return res;
}

bool ok(vector<int> &h)
{
    for(auto &f : h)
        {
            for(auto &s : vecini[f])
                {
                    if(abs(ans[f] + ans[s.first] - s.second) > eps)
                        return 0;
                }
        }

    return 1;
}

void solve(vector<int> &comp)
{
    for(auto &v : comp)
        {
            if(fix[v])
                {
                    vector<pid> h; go(v,ans[v],h);
                    for(auto &it : h) ans[it.first] = it.second;
                    return;
                }
        }

    long double mini = 1e18; vector<pid> res;
    uniform_int_distribution<int> d(0,comp.size()-1);
    for(int ty = 0; ty < 3; ty++)
        {
            int mumu = comp[d(rng)];
            for(auto &val : bulan)
            {
                for(auto &it : comp) viz[it] = 0;
                vector<pid> h; go(mumu,val,h); double now = ab(h);
                if(now < mini && ok(comp))
                    {
                        mini = now;
                        res.swap(h);
                    }
            }
        }

    for(auto &it : res)
        ans[it.first] = it.second;
}

int main()
{
    int n,m,a,b,c; cin >> n >> m;
    for(int i = 1; i <= m ; i++)
        {
            cin >> a >> b >> c;
            vecini[a].push_back({b,c});
            vecini[b].push_back({a,c});
            if(a == b)
                {
                    fix[a] = 1;
                    ans[a] = (1.0 * c / 2);
                }
        }

    vector<vector<int>> comps;
    for(int i = 1; i <= n ; i++)
        {
            if(!viz[i])
                {
                    vector<int> comp;
                    dfs(i,comp); comps.push_back(comp);
                }
        }

    viz.reset();
    for(auto &it : comps)
        solve(it);

    bool okk = 1;
    for(auto &c : comps) okk &= ok(c);

    if(!okk) cout << "NO";
    else
    {
            cout << "YES\n";
            for(int i = 1; i <= n ; i++)
                cout << fixed << setprecision(2) << ans[i] << " ";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB answer = YES
2 Correct 1 ms 2904 KB answer = YES
3 Correct 1 ms 2652 KB answer = YES
4 Correct 1 ms 2652 KB answer = NO
5 Correct 1 ms 2652 KB answer = YES
6 Correct 1 ms 2652 KB answer = YES
7 Correct 1 ms 2652 KB answer = YES
8 Correct 1 ms 2652 KB answer = YES
9 Correct 2 ms 2652 KB answer = NO
10 Correct 1 ms 2652 KB answer = YES
11 Correct 1 ms 2652 KB answer = YES
12 Correct 1 ms 2652 KB answer = NO
13 Correct 1 ms 2652 KB answer = YES
14 Correct 1 ms 2648 KB answer = YES
15 Correct 1 ms 2652 KB answer = YES
16 Correct 1 ms 2652 KB answer = YES
17 Correct 1 ms 2652 KB answer = YES
18 Correct 1 ms 2652 KB answer = YES
19 Correct 1 ms 2652 KB answer = YES
20 Correct 1 ms 2652 KB answer = YES
21 Correct 1 ms 2652 KB answer = YES
22 Correct 1 ms 2652 KB answer = NO
23 Correct 1 ms 2648 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB answer = YES
2 Correct 1 ms 2904 KB answer = YES
3 Correct 1 ms 2652 KB answer = YES
4 Correct 1 ms 2652 KB answer = NO
5 Correct 1 ms 2652 KB answer = YES
6 Correct 1 ms 2652 KB answer = YES
7 Correct 1 ms 2652 KB answer = YES
8 Correct 1 ms 2652 KB answer = YES
9 Correct 2 ms 2652 KB answer = NO
10 Correct 1 ms 2652 KB answer = YES
11 Correct 1 ms 2652 KB answer = YES
12 Correct 1 ms 2652 KB answer = NO
13 Correct 1 ms 2652 KB answer = YES
14 Correct 1 ms 2648 KB answer = YES
15 Correct 1 ms 2652 KB answer = YES
16 Correct 1 ms 2652 KB answer = YES
17 Correct 1 ms 2652 KB answer = YES
18 Correct 1 ms 2652 KB answer = YES
19 Correct 1 ms 2652 KB answer = YES
20 Correct 1 ms 2652 KB answer = YES
21 Correct 1 ms 2652 KB answer = YES
22 Correct 1 ms 2652 KB answer = NO
23 Correct 1 ms 2648 KB answer = NO
24 Correct 1 ms 2652 KB answer = YES
25 Correct 1 ms 2652 KB answer = YES
26 Correct 1 ms 2652 KB answer = YES
27 Correct 1 ms 2652 KB answer = YES
28 Correct 1 ms 2652 KB answer = YES
29 Correct 1 ms 2652 KB answer = YES
30 Correct 1 ms 2652 KB answer = NO
31 Correct 1 ms 2652 KB answer = YES
32 Correct 1 ms 2652 KB answer = YES
33 Correct 1 ms 2648 KB answer = YES
34 Correct 1 ms 2652 KB answer = YES
35 Correct 2 ms 2652 KB answer = YES
36 Correct 1 ms 2652 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB answer = YES
2 Correct 1 ms 2904 KB answer = YES
3 Correct 1 ms 2652 KB answer = YES
4 Correct 1 ms 2652 KB answer = NO
5 Correct 1 ms 2652 KB answer = YES
6 Correct 1 ms 2652 KB answer = YES
7 Correct 1 ms 2652 KB answer = YES
8 Correct 1 ms 2652 KB answer = YES
9 Correct 2 ms 2652 KB answer = NO
10 Correct 1 ms 2652 KB answer = YES
11 Correct 1 ms 2652 KB answer = YES
12 Correct 1 ms 2652 KB answer = NO
13 Correct 1 ms 2652 KB answer = YES
14 Correct 1 ms 2648 KB answer = YES
15 Correct 1 ms 2652 KB answer = YES
16 Correct 1 ms 2652 KB answer = YES
17 Correct 1 ms 2652 KB answer = YES
18 Correct 1 ms 2652 KB answer = YES
19 Correct 1 ms 2652 KB answer = YES
20 Correct 1 ms 2652 KB answer = YES
21 Correct 1 ms 2652 KB answer = YES
22 Correct 1 ms 2652 KB answer = NO
23 Correct 1 ms 2648 KB answer = NO
24 Correct 1 ms 2652 KB answer = YES
25 Correct 1 ms 2652 KB answer = YES
26 Correct 1 ms 2652 KB answer = YES
27 Correct 1 ms 2652 KB answer = YES
28 Correct 1 ms 2652 KB answer = YES
29 Correct 1 ms 2652 KB answer = YES
30 Correct 1 ms 2652 KB answer = NO
31 Correct 1 ms 2652 KB answer = YES
32 Correct 1 ms 2652 KB answer = YES
33 Correct 1 ms 2648 KB answer = YES
34 Correct 1 ms 2652 KB answer = YES
35 Correct 2 ms 2652 KB answer = YES
36 Correct 1 ms 2652 KB answer = YES
37 Correct 2 ms 2652 KB answer = YES
38 Correct 2 ms 2904 KB answer = YES
39 Correct 3 ms 2652 KB answer = YES
40 Correct 4 ms 2908 KB answer = YES
41 Correct 4 ms 2904 KB answer = NO
42 Correct 4 ms 2908 KB answer = YES
43 Correct 4 ms 2652 KB answer = YES
44 Correct 4 ms 2648 KB answer = YES
45 Correct 2 ms 2648 KB answer = YES
46 Correct 3 ms 2652 KB answer = YES
47 Correct 2 ms 2648 KB answer = YES
48 Correct 2 ms 2908 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB answer = YES
2 Correct 1 ms 2904 KB answer = YES
3 Correct 1 ms 2652 KB answer = YES
4 Correct 1 ms 2652 KB answer = NO
5 Correct 1 ms 2652 KB answer = YES
6 Correct 1 ms 2652 KB answer = YES
7 Correct 1 ms 2652 KB answer = YES
8 Correct 1 ms 2652 KB answer = YES
9 Correct 2 ms 2652 KB answer = NO
10 Correct 1 ms 2652 KB answer = YES
11 Correct 1 ms 2652 KB answer = YES
12 Correct 1 ms 2652 KB answer = NO
13 Correct 1 ms 2652 KB answer = YES
14 Correct 1 ms 2648 KB answer = YES
15 Correct 1 ms 2652 KB answer = YES
16 Correct 1 ms 2652 KB answer = YES
17 Correct 1 ms 2652 KB answer = YES
18 Correct 1 ms 2652 KB answer = YES
19 Correct 1 ms 2652 KB answer = YES
20 Correct 1 ms 2652 KB answer = YES
21 Correct 1 ms 2652 KB answer = YES
22 Correct 1 ms 2652 KB answer = NO
23 Correct 1 ms 2648 KB answer = NO
24 Correct 1 ms 2652 KB answer = YES
25 Correct 1 ms 2652 KB answer = YES
26 Correct 1 ms 2652 KB answer = YES
27 Correct 1 ms 2652 KB answer = YES
28 Correct 1 ms 2652 KB answer = YES
29 Correct 1 ms 2652 KB answer = YES
30 Correct 1 ms 2652 KB answer = NO
31 Correct 1 ms 2652 KB answer = YES
32 Correct 1 ms 2652 KB answer = YES
33 Correct 1 ms 2648 KB answer = YES
34 Correct 1 ms 2652 KB answer = YES
35 Correct 2 ms 2652 KB answer = YES
36 Correct 1 ms 2652 KB answer = YES
37 Correct 2 ms 2652 KB answer = YES
38 Correct 2 ms 2904 KB answer = YES
39 Correct 3 ms 2652 KB answer = YES
40 Correct 4 ms 2908 KB answer = YES
41 Correct 4 ms 2904 KB answer = NO
42 Correct 4 ms 2908 KB answer = YES
43 Correct 4 ms 2652 KB answer = YES
44 Correct 4 ms 2648 KB answer = YES
45 Correct 2 ms 2648 KB answer = YES
46 Correct 3 ms 2652 KB answer = YES
47 Correct 2 ms 2648 KB answer = YES
48 Correct 2 ms 2908 KB answer = YES
49 Correct 46 ms 3888 KB answer = YES
50 Correct 43 ms 4248 KB answer = YES
51 Correct 39 ms 4384 KB answer = YES
52 Correct 44 ms 4500 KB answer = NO
53 Correct 4 ms 2904 KB answer = YES
54 Correct 8 ms 2908 KB answer = YES
55 Correct 19 ms 3340 KB answer = YES
56 Correct 40 ms 3816 KB answer = YES
57 Correct 37 ms 3428 KB answer = YES
58 Correct 30 ms 3472 KB answer = YES
59 Correct 10 ms 3420 KB answer = YES
60 Correct 39 ms 3632 KB answer = YES
61 Correct 5 ms 3164 KB answer = YES
62 Correct 106 ms 8496 KB answer = NO
63 Correct 104 ms 8404 KB answer = YES
64 Correct 105 ms 8276 KB answer = NO
65 Correct 104 ms 8404 KB answer = YES
66 Correct 7 ms 2904 KB answer = YES

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB answer = YES
2 Correct 1 ms 2904 KB answer = YES
3 Correct 1 ms 2652 KB answer = YES
4 Correct 1 ms 2652 KB answer = NO
5 Correct 1 ms 2652 KB answer = YES
6 Correct 1 ms 2652 KB answer = YES
7 Correct 1 ms 2652 KB answer = YES
8 Correct 1 ms 2652 KB answer = YES
9 Correct 2 ms 2652 KB answer = NO
10 Correct 1 ms 2652 KB answer = YES
11 Correct 1 ms 2652 KB answer = YES
12 Correct 1 ms 2652 KB answer = NO
13 Correct 1 ms 2652 KB answer = YES
14 Correct 1 ms 2648 KB answer = YES
15 Correct 1 ms 2652 KB answer = YES
16 Correct 1 ms 2652 KB answer = YES
17 Correct 1 ms 2652 KB answer = YES
18 Correct 1 ms 2652 KB answer = YES
19 Correct 1 ms 2652 KB answer = YES
20 Correct 1 ms 2652 KB answer = YES
21 Correct 1 ms 2652 KB answer = YES
22 Correct 1 ms 2652 KB answer = NO
23 Correct 1 ms 2648 KB answer = NO
24 Correct 1 ms 2652 KB answer = YES
25 Correct 1 ms 2652 KB answer = YES
26 Correct 1 ms 2652 KB answer = YES
27 Correct 1 ms 2652 KB answer = YES
28 Correct 1 ms 2652 KB answer = YES
29 Correct 1 ms 2652 KB answer = YES
30 Correct 1 ms 2652 KB answer = NO
31 Correct 1 ms 2652 KB answer = YES
32 Correct 1 ms 2652 KB answer = YES
33 Correct 1 ms 2648 KB answer = YES
34 Correct 1 ms 2652 KB answer = YES
35 Correct 2 ms 2652 KB answer = YES
36 Correct 1 ms 2652 KB answer = YES
37 Correct 2 ms 2652 KB answer = YES
38 Correct 2 ms 2904 KB answer = YES
39 Correct 3 ms 2652 KB answer = YES
40 Correct 4 ms 2908 KB answer = YES
41 Correct 4 ms 2904 KB answer = NO
42 Correct 4 ms 2908 KB answer = YES
43 Correct 4 ms 2652 KB answer = YES
44 Correct 4 ms 2648 KB answer = YES
45 Correct 2 ms 2648 KB answer = YES
46 Correct 3 ms 2652 KB answer = YES
47 Correct 2 ms 2648 KB answer = YES
48 Correct 2 ms 2908 KB answer = YES
49 Correct 46 ms 3888 KB answer = YES
50 Correct 43 ms 4248 KB answer = YES
51 Correct 39 ms 4384 KB answer = YES
52 Correct 44 ms 4500 KB answer = NO
53 Correct 4 ms 2904 KB answer = YES
54 Correct 8 ms 2908 KB answer = YES
55 Correct 19 ms 3340 KB answer = YES
56 Correct 40 ms 3816 KB answer = YES
57 Correct 37 ms 3428 KB answer = YES
58 Correct 30 ms 3472 KB answer = YES
59 Correct 10 ms 3420 KB answer = YES
60 Correct 39 ms 3632 KB answer = YES
61 Correct 5 ms 3164 KB answer = YES
62 Correct 106 ms 8496 KB answer = NO
63 Correct 104 ms 8404 KB answer = YES
64 Correct 105 ms 8276 KB answer = NO
65 Correct 104 ms 8404 KB answer = YES
66 Correct 7 ms 2904 KB answer = YES
67 Correct 454 ms 20904 KB answer = YES
68 Correct 501 ms 21088 KB answer = YES
69 Correct 496 ms 21812 KB answer = YES
70 Execution timed out 730 ms 24820 KB Time limit exceeded
71 Halted 0 ms 0 KB -