답안 #228136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228136	2020-04-30T03:54:16 Z	qkxwsm	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	130 ms	9520 KB

#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

static const int MAXN = 10013;
static const int MAGIC = 60;

static int N;
static vi edge[MAXN];
static int dsu[MAXN];
static vi nodes[MAXN];
static bool vis[MAXN], inside[MAXN];
static int parent[MAXN], label[MAXN];

static int get(int u)
{
    return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
static bool merge(int u, int v)
{
    u = get(u);
    v = get(v);
    if (u == v)
    {
        return false;
    }
    dsu[u] = v;
    return true;
}
static void gen()
{
    //generates all the labels for all the nodes.
    parent[0] = N;
    queue<int> q; q.push(0);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        // cerr << "u = " << u << endl;
        label[u] = SZ(nodes[0]);
        nodes[0].PB(u);
        vis[u] = true;
        for (int v : edge[u])
        {
            if (vis[v])
            {
                continue;
            }
            parent[v] = u;
            q.push(v);
        }
        if (SZ(nodes[0]) == MAGIC)
        {
            break;
        }
    }
    FOR(i, 1, SZ(nodes[0]))
    {
        nodes[nodes[0][i]] = nodes[0];
    }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = true;
        for (int v : nodes[parent[u]])
        {
            inside[v] = true;
        }
        nodes[u] = nodes[parent[u]];
        FOR(i, 0, SZ(nodes[parent[u]]))
        {
            int v = nodes[parent[u]][i];
            if (v == parent[u]) continue;
            int c = 0;
            for (int x : edge[v])
            {
                if (inside[x]) c++;
            }
            if (c == 1)
            {
                label[u] = label[v];
                nodes[u][i] = u;
                break;
            }
        }
        for (int v : nodes[parent[u]])
        {
            inside[v] = false;
            //you just wanna find any leaf, except w
        }
        for (int v : edge[u])
        {
            if (vis[v])
            {
                continue;
            }
            parent[v] = u;
            q.push(v);
        }
    }
}

void Joi(int n, int m, int e1[], int e2[], ll val, int subtask)
{
    N = n;
    iota(dsu, dsu + N, 0);
    FOR(i, 0, m)
    {
        int u = e1[i], v = e2[i];
        if (merge(u, v))
        {
            edge[u].PB(v);
            edge[v].PB(u);
        }
    }
    gen();
    FOR(i, 0, N)
    {
        int x = label[i];
        MessageBoard(i, (val & (1ll << x)) ? 1 : 0);
    }
    //generate a tree for each node.
}

#include "Ioi.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

static const int MAXN = 10013;
static const int MAGIC = 60;

static int N;
static vi edge[MAXN];
static int dsu[MAXN];
static vi nodes[MAXN];
static bool vis[MAXN], inside[MAXN];
static int parent[MAXN], label[MAXN];
static ll ans;

static int get(int u)
{
    return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
static bool merge(int u, int v)
{
    u = get(u);
    v = get(v);
    if (u == v)
    {
        return false;
    }
    dsu[u] = v;
    return true;
}
static void gen()
{
    //generates all the labels for all the nodes.
    parent[0] = N;
    queue<int> q; q.push(0);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        cerr << "u = " << u << endl;
        label[u] = SZ(nodes[0]);
        nodes[0].PB(u);
        vis[u] = true;
        for (int v : edge[u])
        {
            if (vis[v])
            {
                continue;
            }
            parent[v] = u;
            q.push(v);
        }
        if (SZ(nodes[0]) == MAGIC)
        {
            break;
        }
    }
    FOR(i, 1, SZ(nodes[0]))
    {
        nodes[nodes[0][i]] = nodes[0];
    }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        cerr << "u = " << u << endl;
        vis[u] = true;
        for (int v : nodes[parent[u]])
        {
            inside[v] = true;
        }
        nodes[u] = nodes[parent[u]];
        FOR(i, 0, SZ(nodes[parent[u]]))
        {
            int v = nodes[parent[u]][i];
            if (v == parent[u]) continue;
            int c = 0;
            for (int x : edge[v])
            {
                if (inside[x]) c++;
            }
            if (c == 1)
            {
                label[u] = label[v];
                nodes[u][i] = u;
                break;
            }
        }
        for (int v : nodes[parent[u]])
        {
            inside[v] = false;
            //you just wanna find any leaf, except w
        }
        for (int v : edge[u])
        {
            if (vis[v])
            {
                continue;
            }
            parent[v] = u;
            q.push(v);
        }
    }
}
static void dfs(int u, int p, int va)
{
    // cerr << "DFS " << u << ' ' << p << endl;
    int x = label[u];
    if (va)
    {
        ans |= (1ll << x);
    }
    for (int v : edge[u])
    {
        // cerr << "try " << u << ' ' << v << endl;
        if (v == p || !inside[v])
        {
            continue;
        }
        int vv = Move(v);
        dfs(v, u, vv);
        Move(u);
    }
}

ll Ioi(int n, int m, int e1[], int e2[], int st, int va, int subtask)
{
    N = n;
    iota(dsu, dsu + N, 0);
    FOR(i, 0, m)
    {
        int u = e1[i], v = e2[i];
        if (merge(u, v))
        {
            edge[u].PB(v);
            edge[v].PB(u);
            // cerr << "edge " << u << ' ' << v << endl;
        }
    }
    gen();
    FOR(i, 0, N)
    {
        inside[i] = false;
    }
    for (int u : nodes[st])
    {
        inside[u] = true;
        // cerr << "inside " << u << endl;
    }
    dfs(st, N, va);
    cerr << "Return " << ans << endl;
    return ans;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	2052 KB	Output is correct
2	Correct	11 ms	2028 KB	Output is correct
3	Correct	12 ms	1712 KB	Output is correct
4	Correct	10 ms	1796 KB	Output is correct
5	Correct	10 ms	2040 KB	Output is correct
6	Correct	11 ms	2012 KB	Output is correct
7	Correct	12 ms	1972 KB	Output is correct
8	Correct	12 ms	1972 KB	Output is correct
9	Correct	12 ms	1988 KB	Output is correct
10	Correct	11 ms	1808 KB	Output is correct
11	Correct	14 ms	2216 KB	Output is correct
12	Correct	10 ms	2052 KB	Output is correct
13	Correct	12 ms	1936 KB	Output is correct
14	Correct	12 ms	1960 KB	Output is correct
15	Correct	12 ms	1936 KB	Output is correct
16	Correct	12 ms	2036 KB	Output is correct
17	Correct	12 ms	1968 KB	Output is correct
18	Correct	12 ms	1972 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	114 ms	9172 KB	Output is correct
2	Correct	110 ms	9276 KB	Output is correct
3	Correct	114 ms	9180 KB	Output is correct
4	Correct	108 ms	8520 KB	Output is correct
5	Correct	104 ms	8540 KB	Output is correct
6	Correct	101 ms	8784 KB	Output is correct
7	Correct	100 ms	8740 KB	Output is correct
8	Correct	97 ms	8764 KB	Output is correct
9	Correct	100 ms	8792 KB	Output is correct
10	Correct	110 ms	8748 KB	Output is correct
11	Correct	111 ms	8984 KB	Output is correct
12	Correct	90 ms	8284 KB	Output is correct
13	Correct	100 ms	8288 KB	Output is correct
14	Correct	90 ms	8544 KB	Output is correct
15	Correct	102 ms	8744 KB	Output is correct
16	Correct	94 ms	8740 KB	Output is correct
17	Correct	97 ms	8780 KB	Output is correct
18	Correct	117 ms	8884 KB	Output is correct
19	Correct	102 ms	8740 KB	Output is correct
20	Correct	92 ms	8788 KB	Output is correct
21	Correct	90 ms	8612 KB	Output is correct
22	Correct	96 ms	8740 KB	Output is correct
23	Correct	105 ms	8784 KB	Output is correct
24	Correct	99 ms	8796 KB	Output is correct
25	Correct	103 ms	8784 KB	Output is correct
26	Correct	99 ms	8796 KB	Output is correct
27	Correct	98 ms	8792 KB	Output is correct
28	Correct	102 ms	8712 KB	Output is correct
29	Correct	98 ms	8260 KB	Output is correct
30	Correct	92 ms	8552 KB	Output is correct
31	Correct	11 ms	1868 KB	Output is correct
32	Correct	11 ms	1928 KB	Output is correct
33	Correct	13 ms	1976 KB	Output is correct
34	Correct	11 ms	2032 KB	Output is correct
35	Correct	10 ms	2036 KB	Output is correct
36	Correct	10 ms	2020 KB	Output is correct
37	Correct	10 ms	2048 KB	Output is correct
38	Correct	10 ms	2052 KB	Output is correct
39	Correct	10 ms	2060 KB	Output is correct
40	Correct	10 ms	2032 KB	Output is correct
41	Correct	10 ms	2040 KB	Output is correct
42	Correct	10 ms	2048 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	1880 KB	Output is correct
2	Correct	11 ms	2044 KB	Output is correct
3	Correct	11 ms	1944 KB	Output is correct
4	Correct	23 ms	3084 KB	Output is correct
5	Correct	23 ms	2964 KB	Output is correct
6	Correct	23 ms	3104 KB	Output is correct
7	Correct	24 ms	3108 KB	Output is correct
8	Correct	22 ms	2876 KB	Output is correct
9	Correct	92 ms	8824 KB	Output is correct
10	Correct	93 ms	8748 KB	Output is correct
11	Correct	93 ms	8668 KB	Output is correct
12	Correct	11 ms	2040 KB	Output is correct
13	Correct	10 ms	2048 KB	Output is correct
14	Correct	10 ms	2044 KB	Output is correct
15	Correct	10 ms	1800 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	118 ms	9436 KB	Output is correct
2	Correct	110 ms	9272 KB	Output is correct
3	Correct	112 ms	9112 KB	Output is correct
4	Correct	100 ms	8768 KB	Output is correct
5	Correct	101 ms	8532 KB	Output is correct
6	Correct	100 ms	8788 KB	Output is correct
7	Correct	102 ms	8792 KB	Output is correct
8	Correct	104 ms	8908 KB	Output is correct
9	Correct	101 ms	8740 KB	Output is correct
10	Correct	109 ms	8980 KB	Output is correct
11	Correct	106 ms	8744 KB	Output is correct
12	Correct	89 ms	8268 KB	Output is correct
13	Correct	86 ms	8284 KB	Output is correct
14	Correct	94 ms	8512 KB	Output is correct
15	Correct	98 ms	8752 KB	Output is correct
16	Correct	101 ms	8784 KB	Output is correct
17	Correct	96 ms	8820 KB	Output is correct
18	Correct	106 ms	8732 KB	Output is correct
19	Correct	102 ms	8868 KB	Output is correct
20	Correct	94 ms	8632 KB	Output is correct
21	Correct	93 ms	8708 KB	Output is correct
22	Correct	107 ms	8792 KB	Output is correct
23	Correct	97 ms	8788 KB	Output is correct
24	Correct	100 ms	8788 KB	Output is correct
25	Correct	98 ms	8788 KB	Output is correct
26	Correct	100 ms	8788 KB	Output is correct
27	Correct	101 ms	8788 KB	Output is correct
28	Correct	97 ms	8792 KB	Output is correct
29	Correct	93 ms	8292 KB	Output is correct
30	Correct	94 ms	8472 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	111 ms	9276 KB	Output is correct
2	Correct	113 ms	9520 KB	Output is correct
3	Correct	113 ms	9520 KB	Output is correct
4	Correct	101 ms	8784 KB	Output is correct
5	Correct	99 ms	8780 KB	Output is correct
6	Correct	102 ms	8784 KB	Output is correct
7	Correct	103 ms	8760 KB	Output is correct
8	Correct	101 ms	9016 KB	Output is correct
9	Correct	101 ms	8888 KB	Output is correct
10	Correct	106 ms	8976 KB	Output is correct
11	Correct	112 ms	8968 KB	Output is correct
12	Correct	85 ms	8284 KB	Output is correct
13	Correct	103 ms	8180 KB	Output is correct
14	Correct	90 ms	8392 KB	Output is correct
15	Correct	107 ms	8788 KB	Output is correct
16	Correct	96 ms	8792 KB	Output is correct
17	Correct	98 ms	8884 KB	Output is correct
18	Correct	102 ms	8772 KB	Output is correct
19	Correct	105 ms	8776 KB	Output is correct
20	Correct	96 ms	8784 KB	Output is correct
21	Correct	94 ms	8712 KB	Output is correct
22	Correct	98 ms	8788 KB	Output is correct
23	Correct	105 ms	8788 KB	Output is correct
24	Correct	106 ms	8760 KB	Output is correct
25	Correct	107 ms	8832 KB	Output is correct
26	Correct	105 ms	8792 KB	Output is correct
27	Correct	130 ms	8884 KB	Output is correct
28	Correct	110 ms	8768 KB	Output is correct
29	Correct	104 ms	8284 KB	Output is correct
30	Correct	99 ms	8616 KB	Output is correct
31	Correct	11 ms	2020 KB	Output is correct
32	Correct	12 ms	2016 KB	Output is correct
33	Correct	13 ms	1948 KB	Output is correct
34	Correct	11 ms	1928 KB	Output is correct
35	Correct	12 ms	1928 KB	Output is correct
36	Correct	11 ms	1800 KB	Output is correct
37	Correct	10 ms	1928 KB	Output is correct
38	Correct	11 ms	1800 KB	Output is correct
39	Correct	10 ms	1900 KB	Output is correct
40	Correct	11 ms	1928 KB	Output is correct
41	Correct	11 ms	2028 KB	Output is correct
42	Correct	11 ms	1928 KB	Output is correct

답안 #228136

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 55.0 / 55.0

Subtask #5 17.0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
55.0 / 55.0

Subtask #5
17.0 / 17.0