답안 #1069139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1069139	2024-08-21T16:18:32 Z	Jarif_Rahman	Amusement Park (JOI17_amusement_park)	C++17	65 / 100	36 ms	16648 KB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

namespace {
    const int N = 10000;
    const int k = 60;
    int n, m;
    vector<int> graph[N];
    vector<int> tree[N];
    bitset<N> bl;
    int in[N], out[N];

    int msg[N];
    vector<int> nodes[N];

    int _p = 0;
    void spanning_tree(int nd, int ss){
        if(bl[nd]) return;
        bl[nd] = 1;
        if(ss != -1) tree[ss].push_back(nd);
        in[nd] = _p++;
        for(int x: graph[nd]) spanning_tree(x, nd);
        out[nd] = _p;
    }

    void create_initial_group(int nd){
        if(nodes[0].size() == k) return;
        nodes[0].push_back(nd);
        for(int x: tree[nd]) create_initial_group(x);
    }

    bool contains(int x, int y){
        return in[x] <= in[y] && out[x] >= out[y];
    }

    void dfs(int nd, int ss){
        if(!nodes[nd].empty()){
            for(int x: tree[nd]) dfs(x, nd);
            return;
        }
        nodes[nd] = nodes[ss];
        nodes[nd].push_back(nd);
        sort(nodes[nd].begin(), nodes[nd].end(), [&](int a, int b){
            return in[a] < in[b];
        });

        int rem = -1;
        bool ok = contains(nodes[nd][0], nodes[nd][1]);
        for(int x: nodes[nd]){
            if(x == nodes[nd][0] || x == nodes[nd][1]) continue;
            ok&=contains(nodes[nd][1], x);
        }
        if(ok) rem = nodes[nd][0];
        else{
            for(int x: nodes[nd]) if(x != nd){
                bool ok = 1;
                for(int y: nodes[nd]) if(y != x)
                    ok&=!contains(x, y);
                if(ok){
                    rem = x;
                    break;
                }
            }
        }
        msg[nd] = msg[rem];
        nodes[nd].erase(find(nodes[nd].begin(), nodes[nd].end(), rem));

        for(int x: tree[nd]) dfs(x, nd);
    }
}

void Joi(int _n, int _m, int A[], int B[], ll X, int T){
    n = _n, m = _m;
    for(int i = 0; i < m; i++){
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }

    spanning_tree(0, -1);
    create_initial_group(0);
    for(int x: nodes[0]) if(x) nodes[x] = nodes[0];
    for(int i = 0; i < k; i++) msg[nodes[0][i]] = i;
    dfs(0, -1);

    vector<int> bin;
    for(int i = 0; i < k; i++){
        bin.push_back(X%2);
        X/=2;
    }

    for(int i = 0; i < n; i++) MessageBoard(i, bin[msg[i]]);
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;


namespace {
    const int N = 10000;
    const int k = 60;
    int n, m;
    vector<int> graph[N];
    vector<int> tree[N];
    bitset<N> bl;
    int in[N], out[N];

    int msg[N];
    vector<int> nodes[N];

    int _p = 0;
    void spanning_tree(int nd, int ss){
        if(bl[nd]) return;
        bl[nd] = 1;
        if(ss != -1) tree[ss].push_back(nd);
        in[nd] = _p++;
        for(int x: graph[nd]) spanning_tree(x, nd);
        out[nd] = _p;
    }

    void create_initial_group(int nd){
        if(nodes[0].size() == k) return;
        nodes[0].push_back(nd);
        for(int x: tree[nd]) create_initial_group(x);
    }

    bool contains(int x, int y){
        return in[x] <= in[y] && out[x] >= out[y];
    }

    void dfs(int nd, int ss){
        if(!nodes[nd].empty()){
            for(int x: tree[nd]) dfs(x, nd);
            return;
        }
        nodes[nd] = nodes[ss];
        nodes[nd].push_back(nd);
        sort(nodes[nd].begin(), nodes[nd].end(), [&](int a, int b){
            return in[a] < in[b];
        });

        int rem = -1;
        bool ok = contains(nodes[nd][0], nodes[nd][1]);
        for(int x: nodes[nd]){
            if(x == nodes[nd][0] || x == nodes[nd][1]) continue;
            ok&=contains(nodes[nd][1], x);
        }
        if(ok) rem = nodes[nd][0];
        else{
            for(int x: nodes[nd]) if(x != nd){
                bool ok = 1;
                for(int y: nodes[nd]) if(y != x)
                    ok&=!contains(x, y);
                if(ok){
                    rem = x;
                    break;
                }
            }
        }
        msg[nd] = msg[rem];
        nodes[nd].erase(find(nodes[nd].begin(), nodes[nd].end(), rem));

        for(int x: tree[nd]) dfs(x, nd);
    }

    vector<int> bin(k);
    vector<int> tree2[N];

    void dfs2(int nd, int ss){
        for(int x: tree2[nd]) if(x != ss){
            bin[msg[x]] = Move(x);
            dfs2(x, nd);
            Move(nd);
        }
    }
}


ll Ioi(int _n, int _m, int A[], int B[], int p, int v, int T){
    n = _n, m = _m;
    for(int i = 0; i < m; i++){
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }

    spanning_tree(0, -1);
    create_initial_group(0);
    for(int x: nodes[0]) if(x) nodes[x] = nodes[0];
    for(int i = 0; i < k; i++) msg[nodes[0][i]] = i;
    dfs(0, -1);

    vector<bool> in_subtree(n, 0);
    for(int x: nodes[p]) in_subtree[x] = 1;
    for(int i = 0; i < m; i++) if(in_subtree[A[i]] && in_subtree[B[i]]){
        tree2[A[i]].push_back(B[i]);
        tree2[B[i]].push_back(A[i]);
    }

    bin[msg[p]] = v;
    dfs2(p, -1);

    ll X = 0;
    for(int i = 0; i < k; i++) if(bin[i]) X+=(1LL<<i);
    return X;
}

Subtask #1

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2572 KB	Output is correct
2	Correct	2 ms	2592 KB	Output is correct
3	Correct	2 ms	2596 KB	Output is correct
4	Correct	2 ms	2580 KB	Output is correct
5	Correct	2 ms	2576 KB	Output is correct
6	Correct	2 ms	2580 KB	Output is correct
7	Correct	2 ms	2600 KB	Output is correct
8	Correct	3 ms	2588 KB	Output is correct
9	Correct	2 ms	2588 KB	Output is correct
10	Incorrect	2 ms	2848 KB	Wrong Answer [8]
11	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	15960 KB	Output is correct
2	Incorrect	30 ms	16648 KB	Wrong Answer [8]
3	Halted	0 ms	0 KB	-

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2584 KB	Output is correct
2	Correct	2 ms	2592 KB	Output is correct
3	Correct	2 ms	2580 KB	Output is correct
4	Correct	5 ms	4680 KB	Output is correct
5	Correct	4 ms	4688 KB	Output is correct
6	Correct	4 ms	4680 KB	Output is correct
7	Correct	5 ms	4680 KB	Output is correct
8	Correct	4 ms	4684 KB	Output is correct
9	Correct	18 ms	16196 KB	Output is correct
10	Correct	20 ms	16204 KB	Output is correct
11	Correct	18 ms	16196 KB	Output is correct
12	Correct	2 ms	2580 KB	Output is correct
13	Correct	2 ms	2580 KB	Output is correct
14	Correct	2 ms	2592 KB	Output is correct
15	Correct	2 ms	2592 KB	Output is correct

Subtask #4

55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	15868 KB	Output is correct
2	Correct	33 ms	16420 KB	Output is correct
3	Correct	32 ms	16404 KB	Output is correct
4	Correct	31 ms	14356 KB	Output is correct
5	Correct	22 ms	15932 KB	Output is correct
6	Correct	25 ms	14960 KB	Output is correct
7	Correct	23 ms	14832 KB	Output is correct
8	Correct	22 ms	14756 KB	Output is correct
9	Correct	23 ms	14796 KB	Output is correct
10	Correct	19 ms	14252 KB	Output is correct
11	Correct	19 ms	14196 KB	Output is correct
12	Correct	26 ms	13344 KB	Output is correct
13	Correct	22 ms	13348 KB	Output is correct
14	Correct	27 ms	13708 KB	Output is correct
15	Correct	22 ms	14396 KB	Output is correct
16	Correct	27 ms	14408 KB	Output is correct
17	Correct	24 ms	14404 KB	Output is correct
18	Correct	26 ms	14300 KB	Output is correct
19	Correct	26 ms	14412 KB	Output is correct
20	Correct	20 ms	15168 KB	Output is correct
21	Correct	20 ms	14920 KB	Output is correct
22	Correct	23 ms	14900 KB	Output is correct
23	Correct	25 ms	14908 KB	Output is correct
24	Correct	24 ms	14820 KB	Output is correct
25	Correct	23 ms	14916 KB	Output is correct
26	Correct	23 ms	14808 KB	Output is correct
27	Correct	22 ms	14912 KB	Output is correct
28	Correct	25 ms	14844 KB	Output is correct
29	Correct	20 ms	13860 KB	Output is correct
30	Correct	20 ms	14388 KB	Output is correct

Subtask #5

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	30 ms	15976 KB	Wrong Answer [8]
2	Halted	0 ms	0 KB	-