oj.uz

답안 #552464

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
552464 2022-04-23T07:54:11 Z Killer2501 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 68 ms 49760 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];
set<pii> leaf;
set<int> st[N];
void dfs(int u)
{

    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;
        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();
    }
    leaf.insert({0, d[u]});
    if(u != 0)
    {
        int v = d[par[u]];
        leaf.erase({(int)st[d[u]].size(), d[u]});
        leaf.erase({(int)st[v].size(), v});
        st[v].insert(d[u]);
        st[d[u]].insert(v);
        leaf.insert({(int)st[d[u]].size(), d[u]});
        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);
    }
}
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();
    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];
set<pii> leaf;
set<int> st[N];
void dfs(int u)
{

    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;
        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();
    }
    leaf.insert({0, d[u]});
    if(u != 0)
    {
        int v = d[par[u]];
        leaf.erase({(int)st[d[u]].size(), d[u]});
        leaf.erase({(int)st[v].size(), v});
        st[v].insert(d[u]);
        st[d[u]].insert(v);
        leaf.insert({(int)st[d[u]].size(), d[u]});
        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);
    }
}

void cal(int u)
{
    //cout << u <<" "<<d[u]<<" "<<a[d[u]]<<'\n';
    for(int v: adj[u])
    {
        if(a[d[v]] == -1)
        {
            a[d[v]] = Move(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();
    }
    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);
    fill_n(a, M, -1);
    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 14 ms 28968 KB Output is correct
2 Correct 16 ms 28952 KB Output is correct
3 Runtime error 33 ms 43592 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28940 KB Output is correct
2 Correct 15 ms 28884 KB Output is correct
3 Correct 14 ms 28968 KB Output is correct
4 Correct 20 ms 29720 KB Output is correct
5 Correct 19 ms 29636 KB Output is correct
6 Correct 22 ms 29752 KB Output is correct
7 Correct 18 ms 29748 KB Output is correct
8 Correct 19 ms 29764 KB Output is correct
9 Correct 38 ms 33800 KB Output is correct
10 Correct 35 ms 33884 KB Output is correct
11 Correct 35 ms 33876 KB Output is correct
12 Correct 18 ms 28960 KB Output is correct
13 Correct 17 ms 28968 KB Output is correct
14 Correct 19 ms 28960 KB Output is correct
15 Correct 14 ms 28948 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 33224 KB Output is correct
2 Correct 50 ms 33128 KB Output is correct
3 Runtime error 68 ms 49760 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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