oj.uz

Submission #552547

# Submission time Handle Problem Language Result Execution time Memory
552547 2022-04-23T09:40:59 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 3000 ms 51436 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].erase(change.fi);
            leaf.insert({(int)st[x].size(), x});
        }
        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].erase(change.fi);
            leaf.insert({(int)st[x].size(), x});
        }
        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 28940 KB Output is correct
2 Runtime error 26 ms 43496 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 26180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28960 KB Output is correct
2 Correct 15 ms 29000 KB Output is correct
3 Correct 17 ms 28872 KB Output is correct
4 Correct 25 ms 30048 KB Output is correct
5 Correct 26 ms 29992 KB Output is correct
6 Correct 20 ms 30012 KB Output is correct
7 Correct 20 ms 30020 KB Output is correct
8 Correct 20 ms 30016 KB Output is correct
9 Correct 46 ms 35664 KB Output is correct
10 Correct 47 ms 35660 KB Output is correct
11 Correct 49 ms 35596 KB Output is correct
12 Correct 16 ms 28968 KB Output is correct
13 Correct 17 ms 29004 KB Output is correct
14 Correct 18 ms 28876 KB Output is correct
15 Correct 15 ms 29020 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 26176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 51436 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -