oj.uz

답안 #552539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
552539 2022-04-23T09:29:38 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 61 ms 49764 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;
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;
    }
};
bool check(set<int> st, int n)
{
    DSU dsu(n);
    for(int u: st)
    {
        for(int v: adj[u])if(st.find(v) != st.end())dsu.hop(u, v);
    }
    return dsu.m == M-1;
}
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);
    }
}
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);
    assert(check(res, n));
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28960 KB Output is correct
2 Correct 14 ms 28960 KB Output is correct
3 Correct 14 ms 28972 KB Output is correct
4 Correct 14 ms 28968 KB Output is correct
5 Correct 16 ms 28968 KB Output is correct
6 Runtime error 27 ms 43540 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 33176 KB Output is correct
2 Correct 48 ms 33184 KB Output is correct
3 Correct 49 ms 33188 KB Output is correct
4 Correct 38 ms 30560 KB Output is correct
5 Correct 38 ms 31888 KB Output is correct
6 Correct 46 ms 31472 KB Output is correct
7 Correct 43 ms 31496 KB Output is correct
8 Correct 39 ms 31812 KB Output is correct
9 Runtime error 53 ms 47764 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28960 KB Output is correct
2 Correct 16 ms 28968 KB Output is correct
3 Correct 17 ms 28952 KB Output is correct
4 Correct 19 ms 29752 KB Output is correct
5 Correct 18 ms 29768 KB Output is correct
6 Correct 20 ms 29748 KB Output is correct
7 Correct 16 ms 29756 KB Output is correct
8 Correct 19 ms 29680 KB Output is correct
9 Correct 35 ms 33764 KB Output is correct
10 Correct 33 ms 33792 KB Output is correct
11 Correct 33 ms 33808 KB Output is correct
12 Correct 15 ms 28960 KB Output is correct
13 Correct 14 ms 28884 KB Output is correct
14 Correct 14 ms 28868 KB Output is correct
15 Correct 15 ms 28848 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 33036 KB Output is correct
2 Runtime error 61 ms 49764 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 33164 KB Output is correct
2 Correct 50 ms 33176 KB Output is correct
3 Runtime error 60 ms 49628 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -