oj.uz

Submission #552431

# Submission time Handle Problem Language Result Execution time Memory
552431 2022-04-23T07:08:14 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 56 ms 33964 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++;
        leaf.insert({0, d[u]});
    }
    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();
    }
    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 ++)
        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++;
        leaf.insert({0, d[u]});
    }
    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();
    }
    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';
        if(a[i])
            res |= (1ll<<i);
    }
    return res;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28968 KB Output is correct
2 Correct 16 ms 28952 KB Output is correct
3 Incorrect 16 ms 28976 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 33592 KB Output is correct
2 Correct 50 ms 33536 KB Output is correct
3 Incorrect 46 ms 33568 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28956 KB Output is correct
2 Correct 16 ms 28956 KB Output is correct
3 Correct 16 ms 28972 KB Output is correct
4 Correct 17 ms 29744 KB Output is correct
5 Correct 18 ms 29772 KB Output is correct
6 Correct 17 ms 29768 KB Output is correct
7 Correct 18 ms 29752 KB Output is correct
8 Correct 19 ms 29776 KB Output is correct
9 Correct 35 ms 33832 KB Output is correct
10 Correct 34 ms 33864 KB Output is correct
11 Correct 34 ms 33964 KB Output is correct
12 Correct 14 ms 28944 KB Output is correct
13 Correct 15 ms 29204 KB Output is correct
14 Correct 15 ms 28964 KB Output is correct
15 Correct 14 ms 29000 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 33636 KB Output is correct
2 Correct 50 ms 33468 KB Output is correct
3 Incorrect 56 ms 33472 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 33612 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -