oj.uz

Submission #552550

# Submission time Handle Problem Language Result Execution time Memory
552550 2022-04-23T09:42:48 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 84 ms 51784 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())
    {
        leaf.erase({1, d[u]});
        leaf.insert({1, change.fi});
        b[change.fi] = change.se;
        for(int x: stchange)
        {
            leaf.erase({(int)st[x].size(), x});
            st[x].insert(change.fi);
            leaf.insert({(int)st[x].size(), x});
        }
        st[change.fi] = stchange;
        int 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())
    {
        leaf.erase({1, d[u]});
        leaf.insert({1, change.fi});
        b[change.fi] = change.se;
        for(int x: stchange)
        {
            leaf.erase({(int)st[x].size(), x});
            st[x].insert(change.fi);
            leaf.insert({(int)st[x].size(), x});
        }
        st[change.fi] = stchange;
        int 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;
        if(a[d[v]] == -1)
        {
            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);
    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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28960 KB Output is correct
2 Runtime error 29 ms 43560 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 34244 KB Output is correct
2 Runtime error 70 ms 51648 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28940 KB Output is correct
2 Correct 15 ms 28944 KB Output is correct
3 Correct 14 ms 28972 KB Output is correct
4 Correct 20 ms 30064 KB Output is correct
5 Correct 20 ms 29912 KB Output is correct
6 Correct 20 ms 30012 KB Output is correct
7 Correct 19 ms 30012 KB Output is correct
8 Correct 18 ms 29860 KB Output is correct
9 Correct 44 ms 35316 KB Output is correct
10 Correct 48 ms 35244 KB Output is correct
11 Correct 48 ms 35412 KB Output is correct
12 Correct 15 ms 28980 KB Output is correct
13 Correct 15 ms 29108 KB Output is correct
14 Correct 14 ms 28968 KB Output is correct
15 Correct 14 ms 28968 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 34248 KB Output is correct
2 Runtime error 75 ms 51784 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 34256 KB Output is correct
2 Correct 65 ms 34412 KB Output is correct
3 Runtime error 84 ms 51704 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -