oj.uz

Submission #927211

# Submission time Handle Problem Language Result Execution time Memory
927211 2024-02-14T12:15:01 Z Tuanlinh123 Amusement Park (JOI17_amusement_park) C++17
28 / 100
 152 ms 5948 KB 
#include "Joi.h"
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

void Joi(int n, int m, int u[], int v[], ll x, int t) 
{
    vector <vector <ll>> A(n);
    for (ll i=0; i<m; i++)
        A[u[i]].pb(v[i]), A[v[i]].pb(u[i]);
    vector <ll> tin(n, -1); ll Time=0;
    function <void(ll)> dfs=[&](ll u)
    {
        tin[u]=Time, Time=(Time+1)%60;
        MessageBoard(u, (x>>tin[u])&1);
        for (ll v:A[u])
            if (tin[v]==-1)
                dfs(v);
    }; dfs(0);
}

#include "Ioi.h"
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

ll Ioi(int n, int m, int u[], int v[], int p, int cr, int t) 
{
    vector <vector <ll>> A(n);
    for (ll i=0; i<m; i++)
        A[u[i]].pb(v[i]), A[v[i]].pb(u[i]);
    ll Time=0, pos=0;
    vector <pll> realedge;
    vector <ll> order, tin(n, -1); 
    function <void(ll)> dfs=[&](ll u)
    {
        if (u==p) pos=order.size(); order.pb(u);
        tin[u]=Time, Time=(Time+1)%60;
        for (ll v:A[u])
            if (tin[v]==-1)
                realedge.pb({v, u}), dfs(v);
    }; dfs(0);
    for (ll i=0; i<n; i++) A[i].clear();
    for (auto [u, v]:realedge) A[u].pb(v), A[v].pb(u);
    pll best={1e9, 0};
    for (ll i=max(0ll, pos-200); i<=min(pos+200, n-60ll); i++)
    {
        vector <ll> mark(n, 0), dis(n, 0); mark[p]=1;
        for (ll j=i; j<i+60; j++)
            mark[order[j]]=1;
        function <void(ll, ll)> dfs1=[&](ll u, ll pa)
        {
            for (ll v:A[u]) if (v!=pa)
            {
                dfs1(v, u), mark[u]|=mark[v];
                if (mark[v]) dis[u]=max(dis[u], dis[v]+1);
            }
        }; dfs1(p, -1);
        ll cnt=0, Max=0;
        for (ll j=0; j<n; j++)
            cnt+=mark[j], Max=max(Max, dis[j]);
        best=min(best, {(cnt-1)*2-Max, i});
    }
    // assert(best.fi<=120);
    vector <ll> mark(n, 0), pa(n, -1), ism(n, 0);
    vector <pll> dis(n, {0, -1}); 
    for (ll j=best.se; j<best.se+60; j++)
        mark[order[j]]=1;
    function <void(ll)> dfs1=[&](ll u)
    {
        for (ll v:A[u]) if (v!=pa[u])
        {
            pa[v]=u, dfs1(v), mark[u]|=mark[v];
            if (mark[v]) dis[u]=max(dis[u], {dis[v].fi+1, v});
        }
    }; dfs1(p);
    ll Max=p; ism[Max]=1;
    while (dis[Max].se!=-1)
        Max=dis[Max].se, ism[Max]=1;
    ll cnt=0, bit[60]={}; bit[tin[p]]=cr;
    function <void(ll)> answer=[&](ll u)
    {
        for (ll& v:A[u]) if (ism[v] && v!=pa[u])
            {swap(v, A[u].back()); break;}
        for (ll v:A[u])
            if (mark[v] && v!=pa[u])
                bit[tin[v]]=Move(v), cnt++, answer(v);
        if (!ism[u]) bit[tin[pa[u]]]=Move(pa[u]), cnt++;
    }; answer(p);
    // assert(cnt<=120);
    ll ans=0;
    for (ll i=0; i<60; i++)
        if (bit[i]) ans|=1ll<<i;
    return ans;
}

Compilation message

Ioi.cpp: In lambda function:
Ioi.cpp:22:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |         if (u==p) pos=order.size(); order.pb(u);
      |         ^~
Ioi.cpp:22:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |         if (u==p) pos=order.size(); order.pb(u);
      |                                     ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1040 KB Output is correct
2 Correct 0 ms 800 KB Output is correct
3 Correct 2 ms 1492 KB Output is correct
4 Correct 0 ms 800 KB Output is correct
5 Correct 0 ms 792 KB Output is correct
6 Correct 1 ms 788 KB Output is correct
7 Correct 2 ms 796 KB Output is correct
8 Correct 1 ms 796 KB Output is correct
9 Correct 2 ms 1300 KB Output is correct
10 Correct 1 ms 800 KB Output is correct
11 Correct 4 ms 1376 KB Output is correct
12 Correct 0 ms 800 KB Output is correct
13 Correct 1 ms 804 KB Output is correct
14 Correct 2 ms 796 KB Output is correct
15 Correct 1 ms 804 KB Output is correct
16 Correct 2 ms 796 KB Output is correct
17 Correct 1 ms 796 KB Output is correct
18 Correct 2 ms 800 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 5784 KB Output is correct
2 Correct 152 ms 5624 KB Output is correct
3 Correct 151 ms 5832 KB Output is correct
4 Correct 105 ms 3576 KB Output is correct
5 Correct 131 ms 4840 KB Output is correct
6 Correct 122 ms 4008 KB Output is correct
7 Correct 119 ms 4004 KB Output is correct
8 Correct 124 ms 4312 KB Output is correct
9 Correct 123 ms 4264 KB Output is correct
10 Correct 36 ms 3652 KB Output is correct
11 Correct 59 ms 3696 KB Output is correct
12 Correct 86 ms 3664 KB Output is correct
13 Correct 81 ms 3492 KB Output is correct
14 Correct 71 ms 3588 KB Output is correct
15 Correct 121 ms 3516 KB Output is correct
16 Correct 124 ms 3892 KB Output is correct
17 Correct 99 ms 3532 KB Output is correct
18 Correct 106 ms 3592 KB Output is correct
19 Correct 125 ms 3664 KB Output is correct
20 Correct 26 ms 4328 KB Output is correct
21 Correct 25 ms 4424 KB Output is correct
22 Correct 49 ms 4152 KB Output is correct
23 Correct 121 ms 4376 KB Output is correct
24 Correct 111 ms 4168 KB Output is correct
25 Correct 124 ms 4296 KB Output is correct
26 Correct 120 ms 4284 KB Output is correct
27 Correct 113 ms 4244 KB Output is correct
28 Correct 114 ms 4304 KB Output is correct
29 Correct 103 ms 4140 KB Output is correct
30 Correct 106 ms 4164 KB Output is correct
31 Correct 0 ms 800 KB Output is correct
32 Correct 1 ms 1044 KB Output is correct
33 Correct 1 ms 804 KB Output is correct
34 Correct 0 ms 784 KB Output is correct
35 Correct 1 ms 800 KB Output is correct
36 Correct 2 ms 788 KB Output is correct
37 Correct 0 ms 804 KB Output is correct
38 Correct 0 ms 788 KB Output is correct
39 Correct 0 ms 792 KB Output is correct
40 Correct 0 ms 792 KB Output is correct
41 Correct 0 ms 800 KB Output is correct
42 Correct 0 ms 800 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 800 KB Output is correct
2 Correct 0 ms 784 KB Output is correct
3 Correct 1 ms 804 KB Output is correct
4 Correct 6 ms 1588 KB Output is correct
5 Correct 9 ms 1344 KB Output is correct
6 Correct 6 ms 1600 KB Output is correct
7 Correct 8 ms 1676 KB Output is correct
8 Correct 5 ms 1608 KB Output is correct
9 Correct 80 ms 4936 KB Output is correct
10 Correct 43 ms 5084 KB Output is correct
11 Correct 31 ms 5248 KB Output is correct
12 Correct 0 ms 800 KB Output is correct
13 Correct 0 ms 800 KB Output is correct
14 Correct 0 ms 800 KB Output is correct
15 Correct 0 ms 800 KB Output is correct

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 5536 KB Output is correct
2 Correct 145 ms 5948 KB Output is correct
3 Partially correct 144 ms 5832 KB Partially correct
4 Correct 105 ms 3592 KB Output is correct
5 Correct 137 ms 4740 KB Output is correct
6 Correct 120 ms 4240 KB Output is correct
7 Correct 121 ms 4172 KB Output is correct
8 Correct 120 ms 3832 KB Output is correct
9 Correct 130 ms 3960 KB Output is correct
10 Correct 34 ms 3616 KB Output is correct
11 Correct 64 ms 3668 KB Output is correct
12 Correct 83 ms 3496 KB Output is correct
13 Correct 83 ms 3480 KB Output is correct
14 Correct 88 ms 3712 KB Output is correct
15 Correct 117 ms 3516 KB Output is correct
16 Correct 118 ms 3516 KB Output is correct
17 Correct 111 ms 3772 KB Output is correct
18 Correct 105 ms 3628 KB Output is correct
19 Correct 115 ms 3572 KB Output is correct
20 Incorrect 28 ms 4424 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 5668 KB Output is correct
2 Correct 142 ms 5612 KB Output is correct
3 Incorrect 143 ms 5520 KB Output isn't correct
4 Halted 0 ms 0 KB -