oj.uz

답안 #552556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
552556 2022-04-23T09:47:40 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
0 / 100
 107 ms 51524 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)
{
    pii change;
    set<int> stchange;
    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]);
        change.fi = v;
        change.se = b[v];
        d[u] = v;
        leaf.erase(it);
        stchange = st[v];
        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({1, d[u]});
    else leaf.insert({0, d[u]});
    b[d[u]] = u;
    cur.insert(u);
    if(p != -1 && vis[p] && cnt == M)
    {
        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);
    }
    if(!stchange.empty())
    {
        cur.erase(u);
        cur.insert(change.se);
        leaf.erase({1, d[u]});
        leaf.insert({1, change.fi});
        b[change.fi] = change.se;
        for(int x: stchange)
        {
            leaf.erase({(int)st[x].size(), x});
            st[x].insert(change.fi);
            leaf.insert({(int)st[x].size(), x});
        }
        st[change.fi] = stchange;
        int v = d[par[u]];
        leaf.erase({(int)st[v].size(), v});
        st[v].erase(d[u]);
        st[d[u]].erase(v);
        leaf.insert({(int)st[v].size(), 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();
    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 ++)
    {
        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)
{
    pii change;
    set<int> stchange;
    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]);
        change.fi = v;
        change.se = b[v];
        d[u] = v;
        leaf.erase(it);
        stchange = st[v];
        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({1, d[u]});
    else leaf.insert({0, d[u]});
    b[d[u]] = u;
    cur.insert(u);
    if(p == u)ok = true;
    if(p != -1 && vis[p] && cnt == M)
    {
        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);
    }
    if(!stchange.empty())
    {
        cur.erase(u);
        cur.insert(change.se);
        leaf.erase({1, d[u]});
        leaf.insert({1, change.fi});
        b[change.fi] = change.se;
        for(int x: stchange)
        {
            leaf.erase({(int)st[x].size(), x});
            st[x].insert(change.fi);
            leaf.insert({(int)st[x].size(), x});
        }
        st[change.fi] = stchange;
        int v = d[par[u]];
        leaf.erase({(int)st[v].size(), v});
        st[v].erase(d[u]);
        st[d[u]].erase(v);
        leaf.insert({(int)st[v].size(), v});
    }
}
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);
    fill_n(a, M, -1);
    res.erase(P);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 28936 KB Output is correct
2 Runtime error 35 ms 43572 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 100 ms 51524 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 43568 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 91 ms 51476 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 107 ms 51448 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -