oj.uz

Submission #552499

# Submission time Handle Problem Language Result Execution time Memory
552499 2022-04-23T08:44:27 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 63 ms 49952 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;
        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 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;
    ok = false;
    for(int i = 0; i < m; i ++)
    {
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
    }
    DSU dsu(n);
    fill_n(d, n, -1);
    fill_n(par, n, -1);
    fill_n(vis, n, 0);
    dfs(0, P);
    for(int u: res)
    {
        for(int v: adj[u])
            if(res.find(v) != res.end())dsu.hop(u, v);
    }
    assert(dsu.m == M-1);
    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 14 ms 28940 KB Output is correct
2 Correct 14 ms 28956 KB Output is correct
3 Correct 15 ms 29040 KB Output is correct
4 Correct 14 ms 28968 KB Output is correct
5 Correct 15 ms 28928 KB Output is correct
6 Runtime error 24 ms 43552 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 50 ms 33128 KB Output is correct
2 Correct 51 ms 33404 KB Output is correct
3 Correct 49 ms 33536 KB Output is correct
4 Correct 40 ms 30780 KB Output is correct
5 Correct 39 ms 32048 KB Output is correct
6 Correct 38 ms 31596 KB Output is correct
7 Correct 39 ms 31800 KB Output is correct
8 Correct 39 ms 31700 KB Output is correct
9 Runtime error 50 ms 47684 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 15 ms 28976 KB Output is correct
2 Correct 14 ms 29008 KB Output is correct
3 Correct 16 ms 28916 KB Output is correct
4 Correct 19 ms 29648 KB Output is correct
5 Correct 18 ms 29644 KB Output is correct
6 Correct 18 ms 29628 KB Output is correct
7 Correct 18 ms 29620 KB Output is correct
8 Correct 19 ms 29652 KB Output is correct
9 Correct 34 ms 33856 KB Output is correct
10 Correct 34 ms 33712 KB Output is correct
11 Correct 33 ms 33748 KB Output is correct
12 Correct 14 ms 29000 KB Output is correct
13 Correct 15 ms 29160 KB Output is correct
14 Correct 14 ms 28948 KB Output is correct
15 Correct 15 ms 28948 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 33048 KB Output is correct
2 Runtime error 63 ms 49952 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 50 ms 33124 KB Output is correct
2 Correct 47 ms 33572 KB Output is correct
3 Runtime error 61 ms 49932 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -