oj.uz

Submission #552535

# Submission time Handle Problem Language Result Execution time Memory
552535 2022-04-23T09:26:45 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 61 ms 33996 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(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();
    }
    if(u == 0)leaf.insert({0, d[u]});
    else 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(d[par[u]] == (*it).se)++it;
        int v = (*it).se;
        assert(st[v].size() == 1);
        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();
    }
    if(u == 0)leaf.insert({0, d[u]});
    else leaf.insert({1, d[u]});
    b[d[u]] = u;
    cur.insert(u);
    if(p != -1 && vis[p] && cnt == M && res.empty())res = cur;

    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;
        a[d[v]] = Move(v);
        res.erase(v);
        cal(v);
        Move(u);
    }
}
struct DSU
{
    int n, m;
    vector<int> lab;
    DSU(int _n)
    {
        n = _n;
        m = 0;
        lab.resize(n, -1);
    }
    int findp(int u)
    {
        return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
    }
    void hop(int u, int v)
    {
        u = findp(u);
        v = findp(v);
        if(u == v)return;
        if(lab[u] > lab[v])swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        ++m;
    }
};
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;
    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;
    res.erase(P);
    cal(P);
    //assert(res.empty());
    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 16 ms 28900 KB Output is correct
2 Correct 15 ms 28964 KB Output is correct
3 Correct 15 ms 28972 KB Output is correct
4 Correct 15 ms 28868 KB Output is correct
5 Correct 19 ms 28956 KB Output is correct
6 Incorrect 16 ms 28956 KB Wrong Answer [7]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 33500 KB Output is correct
2 Correct 50 ms 33624 KB Output is correct
3 Correct 48 ms 33524 KB Output is correct
4 Correct 47 ms 30560 KB Output is correct
5 Correct 46 ms 32060 KB Output is correct
6 Correct 50 ms 31480 KB Output is correct
7 Correct 46 ms 31568 KB Output is correct
8 Correct 41 ms 31824 KB Output is correct
9 Incorrect 41 ms 31836 KB Wrong Answer [7]
10 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28964 KB Output is correct
2 Correct 17 ms 29012 KB Output is correct
3 Correct 17 ms 28968 KB Output is correct
4 Correct 22 ms 29684 KB Output is correct
5 Correct 27 ms 29764 KB Output is correct
6 Correct 19 ms 29784 KB Output is correct
7 Correct 20 ms 29764 KB Output is correct
8 Correct 18 ms 29776 KB Output is correct
9 Correct 37 ms 33996 KB Output is correct
10 Correct 43 ms 33736 KB Output is correct
11 Correct 38 ms 33736 KB Output is correct
12 Correct 15 ms 28996 KB Output is correct
13 Correct 16 ms 28952 KB Output is correct
14 Correct 16 ms 28964 KB Output is correct
15 Correct 19 ms 28940 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 33444 KB Output is correct
2 Incorrect 53 ms 33448 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 33560 KB Output is correct
2 Correct 55 ms 33364 KB Output is correct
3 Incorrect 61 ms 33492 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -