oj.uz

Submission #552560

# Submission time Handle Problem Language Result Execution time Memory
552560 2022-04-23T09:54:35 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
90 / 100
 70 ms 48624 KB 
#include "Joi.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<int, pii>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+2;
const int M = 60;
const int mod = 1e9+7;
const ll base = 1e6;
const ll inf = 1e9;
int n, m, b[N], a[N], k, d[N], cnt, par[N], f[N];
ll ans;
vector<int> adj[N];
bool vis[N], ok;
set<pii> leaf;
set<int> st[N], cur, res;
void dfs(int u, int p = -1)
{
    pii change;
    set<int> stchange;
    vis[u] = true;
    if(cnt < M)d[u] = cnt++;
    else
    {
        auto it = leaf.begin();
        if(d[par[u]] == (*it).se)++it;
        int v = (*it).se;
        cur.erase(b[v]);
        change.fi = v;
        change.se = b[v];
        d[u] = v;
        leaf.erase(it);
        stchange = st[v];
        for(int x: st[v])
        {
            leaf.erase({(int)st[x].size(), x});
            st[x].erase(v);
            leaf.insert({(int)st[x].size(), x});
        }
        st[v].clear();
    }
    if(u != 0)leaf.insert({1, d[u]});
    else leaf.insert({0, d[u]});
    b[d[u]] = u;
    cur.insert(u);
    if(p == u)ok = true;
    if(ok && cnt == M)
    {
        res = cur;
        ok = false;
    }
    if(u != 0)
    {
        int v = d[par[u]];
        leaf.erase({(int)st[v].size(), v});
        st[v].insert(d[u]);
        st[d[u]].insert(v);
        leaf.insert({(int)st[v].size(), v});
    }
    //cout << u <<" "<<d[u]<<'\n';
    for(int v: adj[u])
    {
        if(vis[v])continue;
        par[v] = u;
        dfs(v, p);
    }
    if(!stchange.empty())
    {
        int v = change.fi;
        cur.erase(u);
        cur.insert(change.se);
        leaf.erase({1, d[u]});
        leaf.insert({1, v});
        b[v] = change.se;
        for(int x: stchange)
        {
            leaf.erase({(int)st[x].size(), x});
            st[x].insert(v);
            leaf.insert({(int)st[x].size(), x});
        }
        st[v] = stchange;
        v = d[par[u]];
        leaf.erase({(int)st[v].size(), v});
        st[v].erase(d[u]);
        st[d[u]].erase(v);
        leaf.insert({(int)st[v].size(), v});
    }
}
void Joi(int n, int m, int A[], int B[], ll x, int T)
{
    for(int i = 0; i < n; i ++)
    {
        st[i].clear();
        adj[i].clear();
    }
    leaf.clear();
    res.clear();
    cur.clear();
    cnt = 0;
    for(int i = 0; i < m; i ++)
    {
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
    }
    fill_n(d, n, -1);
    fill_n(par, n, -1);
    fill_n(vis, n, 0);
    dfs(0);
    for(int i = 0; i < n; i ++)
    {
        MessageBoard(i, (x>>d[i]&1));
    }

}


#include "Ioi.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<int, pii>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+2;
const int M = 60;
const int mod = 1e9+7;
const ll base = 1e6;
const ll inf = 1e9;
int n, m, b[N], a[N], k, d[N], cnt, par[N], f[N];
ll ans;
vector<int> adj[N];
bool vis[N], ok;
set<pii> leaf;
set<int> st[N], cur, res;
void dfs(int u, int p = -1)
{
    pii change;
    set<int> stchange;
    vis[u] = true;
    if(cnt < M)d[u] = cnt++;
    else
    {
        auto it = leaf.begin();
        if(d[par[u]] == (*it).se)++it;
        int v = (*it).se;
        cur.erase(b[v]);
        change.fi = v;
        change.se = b[v];
        d[u] = v;
        leaf.erase(it);
        stchange = st[v];
        for(int x: st[v])
        {
            leaf.erase({(int)st[x].size(), x});
            st[x].erase(v);
            leaf.insert({(int)st[x].size(), x});
        }
        st[v].clear();
    }
    if(u != 0)leaf.insert({1, d[u]});
    else leaf.insert({0, d[u]});
    b[d[u]] = u;
    cur.insert(u);
    if(p == u)ok = true;
    if(ok && cnt == M)
    {
        res = cur;
        ok = false;
    }
    if(u != 0)
    {
        int v = d[par[u]];
        leaf.erase({(int)st[v].size(), v});
        st[v].insert(d[u]);
        st[d[u]].insert(v);
        leaf.insert({(int)st[v].size(), v});
    }
    //cout << u <<" "<<d[u]<<'\n';
    for(int v: adj[u])
    {
        if(vis[v])continue;
        par[v] = u;
        dfs(v, p);
    }
    if(!stchange.empty())
    {
        int v = change.fi;
        cur.erase(u);
        cur.insert(change.se);
        leaf.erase({1, d[u]});
        leaf.insert({1, v});
        b[v] = change.se;
        for(int x: stchange)
        {
            leaf.erase({(int)st[x].size(), x});
            st[x].insert(v);
            leaf.insert({(int)st[x].size(), x});
        }
        st[v] = stchange;
        v = d[par[u]];
        leaf.erase({(int)st[v].size(), v});
        st[v].erase(d[u]);
        st[d[u]].erase(v);
        leaf.insert({(int)st[v].size(), v});
    }
}
void cal(int u)
{
    //cout << u <<" "<<d[u]<<" "<<a[d[u]]<<'\n';
    for(int v: adj[u])
    {
        if(res.find(v) == res.end())continue;
        a[d[v]] = Move(v);
        res.erase(v);
        cal(v);
        Move(u);

    }
}
ll Ioi(int n, int m, int A[], int B[], int P, int V, int T)
{
    for(int i = 0; i < n; i ++)
    {
        st[i].clear();
        adj[i].clear();
    }
    res.clear();
    cur.clear();
    leaf.clear();
    cnt = 0;
    ok = false;
    for(int i = 0; i < m; i ++)
    {
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
    }
    fill_n(d, n, -1);
    fill_n(par, n, -1);
    fill_n(vis, n, 0);
    dfs(0, P);
    fill_n(a, M, -1);
    res.erase(P);
    a[d[P]] = V;
    cal(P);
    ll res = 0;
    for(int i = 0; i < M; i ++)
    {
        //cout << a[i] <<" "<<i<<'\n';
        assert(a[i] != -1);
        if(a[i])
            res |= (1ll<<i);
    }
    return res;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28960 KB Output is correct
2 Correct 14 ms 28964 KB Output is correct
3 Correct 15 ms 28968 KB Output is correct
4 Correct 14 ms 28984 KB Output is correct
5 Correct 14 ms 28880 KB Output is correct
6 Correct 15 ms 28928 KB Output is correct
7 Correct 16 ms 28948 KB Output is correct
8 Correct 14 ms 28932 KB Output is correct
9 Correct 16 ms 28960 KB Output is correct
10 Correct 15 ms 28944 KB Output is correct
11 Correct 19 ms 29408 KB Output is correct
12 Correct 15 ms 28940 KB Output is correct
13 Correct 18 ms 28948 KB Output is correct
14 Correct 16 ms 28964 KB Output is correct
15 Correct 16 ms 28956 KB Output is correct
16 Correct 15 ms 28968 KB Output is correct
17 Correct 16 ms 28968 KB Output is correct
18 Correct 15 ms 28952 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 34020 KB Output is correct
2 Correct 66 ms 34500 KB Output is correct
3 Correct 61 ms 34540 KB Output is correct
4 Correct 47 ms 30544 KB Output is correct
5 Correct 53 ms 32844 KB Output is correct
6 Correct 53 ms 32100 KB Output is correct
7 Correct 51 ms 32208 KB Output is correct
8 Correct 52 ms 32624 KB Output is correct
9 Correct 51 ms 32584 KB Output is correct
10 Correct 38 ms 30684 KB Output is correct
11 Correct 42 ms 30692 KB Output is correct
12 Correct 45 ms 30624 KB Output is correct
13 Correct 43 ms 30580 KB Output is correct
14 Correct 44 ms 30484 KB Output is correct
15 Correct 46 ms 30584 KB Output is correct
16 Correct 49 ms 30636 KB Output is correct
17 Correct 50 ms 30636 KB Output is correct
18 Correct 49 ms 30672 KB Output is correct
19 Correct 47 ms 30672 KB Output is correct
20 Correct 43 ms 33084 KB Output is correct
21 Correct 45 ms 33084 KB Output is correct
22 Correct 55 ms 31780 KB Output is correct
23 Runtime error 60 ms 48624 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28952 KB Output is correct
2 Correct 15 ms 28964 KB Output is correct
3 Correct 15 ms 28944 KB Output is correct
4 Correct 19 ms 30036 KB Output is correct
5 Correct 22 ms 30028 KB Output is correct
6 Correct 23 ms 29916 KB Output is correct
7 Correct 20 ms 29884 KB Output is correct
8 Correct 20 ms 30032 KB Output is correct
9 Correct 46 ms 35440 KB Output is correct
10 Correct 47 ms 35516 KB Output is correct
11 Correct 48 ms 35540 KB Output is correct
12 Correct 14 ms 28968 KB Output is correct
13 Correct 15 ms 28900 KB Output is correct
14 Correct 15 ms 28972 KB Output is correct
15 Correct 14 ms 28972 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 34064 KB Output is correct
2 Correct 67 ms 34500 KB Output is correct
3 Correct 63 ms 34468 KB Output is correct
4 Correct 49 ms 30508 KB Output is correct
5 Correct 52 ms 34112 KB Output is correct
6 Correct 51 ms 32524 KB Output is correct
7 Correct 49 ms 32560 KB Output is correct
8 Correct 51 ms 31640 KB Output is correct
9 Correct 52 ms 32120 KB Output is correct
10 Correct 37 ms 30744 KB Output is correct
11 Correct 39 ms 30764 KB Output is correct
12 Correct 43 ms 30584 KB Output is correct
13 Correct 44 ms 30556 KB Output is correct
14 Correct 45 ms 30540 KB Output is correct
15 Correct 47 ms 30580 KB Output is correct
16 Correct 50 ms 30644 KB Output is correct
17 Correct 49 ms 30640 KB Output is correct
18 Correct 46 ms 30608 KB Output is correct
19 Correct 52 ms 30592 KB Output is correct
20 Correct 45 ms 32992 KB Output is correct
21 Correct 44 ms 33212 KB Output is correct
22 Correct 50 ms 32544 KB Output is correct
23 Correct 51 ms 32276 KB Output is correct
24 Correct 52 ms 32288 KB Output is correct
25 Correct 50 ms 32572 KB Output is correct
26 Correct 51 ms 32520 KB Output is correct
27 Correct 51 ms 32724 KB Output is correct
28 Correct 51 ms 32036 KB Output is correct
29 Correct 50 ms 32096 KB Output is correct
30 Correct 51 ms 32336 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 34136 KB Output is correct
2 Correct 65 ms 34700 KB Output is correct
3 Correct 61 ms 34472 KB Output is correct
4 Correct 50 ms 30540 KB Output is correct
5 Correct 54 ms 34708 KB Output is correct
6 Correct 52 ms 32036 KB Output is correct
7 Correct 54 ms 31856 KB Output is correct
8 Correct 56 ms 32804 KB Output is correct
9 Correct 54 ms 32204 KB Output is correct
10 Correct 40 ms 30780 KB Output is correct
11 Correct 39 ms 30768 KB Output is correct
12 Correct 43 ms 30468 KB Output is correct
13 Correct 41 ms 30472 KB Output is correct
14 Correct 45 ms 30540 KB Output is correct
15 Correct 52 ms 30632 KB Output is correct
16 Correct 47 ms 30640 KB Output is correct
17 Correct 48 ms 30560 KB Output is correct
18 Correct 48 ms 30732 KB Output is correct
19 Correct 49 ms 30660 KB Output is correct
20 Correct 45 ms 33076 KB Output is correct
21 Correct 47 ms 33084 KB Output is correct
22 Correct 51 ms 32312 KB Output is correct
23 Correct 51 ms 32184 KB Output is correct
24 Correct 53 ms 32144 KB Output is correct
25 Correct 51 ms 32168 KB Output is correct
26 Correct 51 ms 31844 KB Output is correct
27 Correct 52 ms 32976 KB Output is correct
28 Correct 53 ms 33076 KB Output is correct
29 Correct 47 ms 32472 KB Output is correct
30 Correct 49 ms 32504 KB Output is correct
31 Correct 14 ms 28964 KB Output is correct
32 Correct 14 ms 28976 KB Output is correct
33 Correct 15 ms 28892 KB Output is correct
34 Correct 14 ms 28960 KB Output is correct
35 Correct 14 ms 28964 KB Output is correct
36 Correct 16 ms 28976 KB Output is correct
37 Correct 17 ms 28924 KB Output is correct
38 Correct 16 ms 28892 KB Output is correct
39 Correct 14 ms 28900 KB Output is correct
40 Correct 16 ms 28972 KB Output is correct
41 Correct 14 ms 28948 KB Output is correct
42 Correct 14 ms 28964 KB Output is correct