oj.uz

Submission #552474

# Submission time Handle Problem Language Result Execution time Memory
552474 2022-04-23T08:15:03 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 66 ms 49868 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)
{

    vis[u] = true;
    if(cnt < M)d[u] = cnt++;
    else
    {
        auto it = leaf.begin();
        if(u != 0 && d[par[u]] == (*it).se)++it;
        int v = (*it).se;
        cur.erase(b[v]);
        d[u] = v;
        leaf.erase(it);
        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();
    }
    leaf.insert({1, 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);
    }
}

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 ++)
    {
        assert(d[i] != -1);
        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)
{

    vis[u] = true;
    if(cnt < M)d[u] = cnt++;
    else
    {
        auto it = leaf.begin();
        if(u != 0 && d[par[u]] == (*it).se)++it;
        int v = (*it).se;
        cur.erase(b[v]);
        d[u] = v;
        leaf.erase(it);
        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();
    }
    leaf.insert({1, 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);
    }
}
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);
    assert(cnt == M);
    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 15 ms 28992 KB Output is correct
2 Correct 16 ms 28968 KB Output is correct
3 Correct 17 ms 29012 KB Output is correct
4 Correct 16 ms 28972 KB Output is correct
5 Correct 18 ms 28920 KB Output is correct
6 Runtime error 26 ms 43812 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 33268 KB Output is correct
2 Correct 56 ms 33456 KB Output is correct
3 Correct 57 ms 33484 KB Output is correct
4 Correct 44 ms 30748 KB Output is correct
5 Correct 42 ms 32060 KB Output is correct
6 Correct 43 ms 31552 KB Output is correct
7 Correct 39 ms 31660 KB Output is correct
8 Correct 41 ms 31840 KB Output is correct
9 Runtime error 55 ms 47820 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28972 KB Output is correct
2 Correct 18 ms 28840 KB Output is correct
3 Correct 15 ms 28916 KB Output is correct
4 Correct 19 ms 29548 KB Output is correct
5 Correct 20 ms 29628 KB Output is correct
6 Correct 20 ms 29600 KB Output is correct
7 Correct 23 ms 29672 KB Output is correct
8 Correct 19 ms 29640 KB Output is correct
9 Correct 36 ms 33796 KB Output is correct
10 Correct 37 ms 33592 KB Output is correct
11 Correct 38 ms 33736 KB Output is correct
12 Correct 18 ms 28932 KB Output is correct
13 Correct 16 ms 29000 KB Output is correct
14 Correct 16 ms 28996 KB Output is correct
15 Correct 17 ms 28956 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 33464 KB Output is correct
2 Runtime error 66 ms 49868 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 56 ms 33392 KB Output is correct
2 Correct 53 ms 33356 KB Output is correct
3 Runtime error 65 ms 49848 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -