oj.uz

Submission #552460

# Submission time Handle Problem Language Result Execution time Memory
552460 2022-04-23T07:51:05 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 65 ms 50072 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];
set<pii> leaf;
set<int> st[N];
void dfs(int u)
{

    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;
        d[u] = v;
        leaf.erase(it);
        for(int x: st[v])
        {
            leaf.erase({st[x].size(), x});
            st[x].erase(v);
            leaf.insert({st[x].size(), x});
        }
        st[v].clear();
    }
    leaf.insert({0, d[u]});
    if(u != 0)
    {
        int v = d[par[u]];
        leaf.erase({st[d[u]].size(), d[u]});
        leaf.erase({st[v].size(), v});
        st[v].insert(d[u]);
        st[d[u]].insert(v);
        leaf.insert({st[d[u]].size(), d[u]});
        leaf.insert({st[v].size(), v});
    }
    //cout << u <<" "<<d[u]<<'\n';
    for(int v: adj[u])
    {
        if(vis[v])continue;
        par[v] = u;
        dfs(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();
    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];
set<pii> leaf;
set<int> st[N];
void dfs(int u)
{

    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;
        d[u] = v;
        leaf.erase(it);
        for(int x: st[v])
        {
            leaf.erase({st[x].size(), x});
            st[x].erase(v);
            leaf.insert({st[x].size(), x});
        }
        st[v].clear();
    }
    leaf.insert({0, d[u]});
    if(u != 0)
    {
        int v = d[par[u]];
        leaf.erase({st[d[u]].size(), d[u]});
        leaf.erase({st[v].size(), v});
        st[v].insert(d[u]);
        st[d[u]].insert(v);
        leaf.insert({st[d[u]].size(), d[u]});
        leaf.insert({st[v].size(), v});
    }
    //cout << u <<" "<<d[u]<<'\n';
    for(int v: adj[u])
    {
        if(vis[v])continue;
        par[v] = u;
        dfs(v);
    }
}

void cal(int u)
{
    //cout << u <<" "<<d[u]<<" "<<a[d[u]]<<'\n';
    for(int v: adj[u])
    {
        if(a[d[v]] == -1)
        {
            a[d[v]] = Move(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();
    }
    leaf.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);
    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 Correct 16 ms 28960 KB Output is correct
3 Runtime error 27 ms 43676 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28964 KB Output is correct
2 Correct 15 ms 28896 KB Output is correct
3 Correct 15 ms 28960 KB Output is correct
4 Correct 18 ms 29656 KB Output is correct
5 Correct 19 ms 29776 KB Output is correct
6 Correct 18 ms 29824 KB Output is correct
7 Correct 18 ms 29752 KB Output is correct
8 Correct 18 ms 29780 KB Output is correct
9 Correct 34 ms 33968 KB Output is correct
10 Correct 44 ms 34000 KB Output is correct
11 Correct 37 ms 34084 KB Output is correct
12 Correct 16 ms 28964 KB Output is correct
13 Correct 16 ms 28872 KB Output is correct
14 Correct 16 ms 28956 KB Output is correct
15 Correct 15 ms 28936 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 33200 KB Output is correct
2 Correct 53 ms 33584 KB Output is correct
3 Runtime error 60 ms 50072 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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