oj.uz

Submission #552488

# Submission time Handle Problem Language Result Execution time Memory
552488 2022-04-23T08:22:36 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 71 ms 49972 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();
    }
    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(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();
    }
    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;
        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((int)res.size() == M);
    fill_n(a, M, -1);
    a[d[P]] = V;
    cal(P);
    assert(res.find(P) != res.end());
    res.erase(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;
}

Compilation message

Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:45:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   45 |     else leaf.insert({1, d[u]});    b[d[u]] = u;
      |     ^~~~
Joi.cpp:45:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   45 |     else leaf.insert({1, d[u]});    b[d[u]] = u;
      |                                     ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28964 KB Output is correct
2 Correct 16 ms 28928 KB Output is correct
3 Correct 16 ms 28948 KB Output is correct
4 Correct 16 ms 28960 KB Output is correct
5 Correct 17 ms 28956 KB Output is correct
6 Runtime error 39 ms 43576 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 53 ms 33444 KB Output is correct
2 Correct 49 ms 33472 KB Output is correct
3 Correct 57 ms 33476 KB Output is correct
4 Correct 41 ms 30556 KB Output is correct
5 Correct 48 ms 31960 KB Output is correct
6 Correct 46 ms 31552 KB Output is correct
7 Correct 39 ms 31688 KB Output is correct
8 Correct 41 ms 31820 KB Output is correct
9 Runtime error 53 ms 47812 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 20 ms 29084 KB Output is correct
2 Correct 17 ms 28908 KB Output is correct
3 Correct 17 ms 28944 KB Output is correct
4 Correct 18 ms 29652 KB Output is correct
5 Correct 18 ms 29636 KB Output is correct
6 Correct 18 ms 29568 KB Output is correct
7 Correct 25 ms 29560 KB Output is correct
8 Correct 19 ms 29640 KB Output is correct
9 Correct 38 ms 33588 KB Output is correct
10 Correct 37 ms 33588 KB Output is correct
11 Correct 36 ms 33728 KB Output is correct
12 Correct 16 ms 28944 KB Output is correct
13 Correct 16 ms 28972 KB Output is correct
14 Correct 17 ms 28952 KB Output is correct
15 Correct 16 ms 28956 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 33400 KB Output is correct
2 Runtime error 71 ms 49972 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 51 ms 33560 KB Output is correct
2 Correct 50 ms 33472 KB Output is correct
3 Runtime error 63 ms 49912 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -