Submission #130617

#	Time	Username	Problem	Language	Result	Execution time	Memory
130617		RezwanArefin01	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	119 ms	35928 KiB

Joi

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

using namespace std;

static const int N = 10010;
static const int B = 60;

static vector<int> adj[N], g[N]; 
static bitset<N> st[N]; 
static int vis[N], bit[N], p[N], comp[N], cnt, idx, deg[N]; 

void gen(int u) {
    vis[u] = 1; 
    for(int v : g[u]) if(!vis[v]) {
        adj[u].push_back(v); 
        adj[v].push_back(u);
        p[v] = u; 
        gen(v); 
    }
}

void mark(int u, int par = -1) {
    ++cnt; 
    st[0][u] = 1; 
    comp[u] = 0;
    bit[u] = cnt - 1;

    for(int v : adj[u]) if(v != par) {
        if(cnt < B) mark(v, u); 
        else break; 
    }
}

void dfs(int u, int par = -1) {
    int leaf = -1; 

    bitset<N> &S = st[comp[u]]; 
    vector<int> nodes;

    for(int i = S._Find_first(); i < S.size(); i = S._Find_next(i)) 
        deg[i] = 0, nodes.push_back(i); 

    for(int v : nodes) {
        if(!v) continue;
        if(S[p[v]]) {
            ++deg[p[v]]; 
            ++deg[v];
        }
    }

    for(int v : nodes) {
        if(deg[v] == 1 && v != u) {
            leaf = v; break; 
        }
    }

    for(int v : adj[u]) if(v != par) {
        if(comp[v] == -1) {
            comp[v] = ++idx;
            st[idx] = st[comp[u]]; 
            bit[v] = bit[leaf]; 
            st[idx][leaf] = 0; 
            st[idx][v] = 1; 
        } dfs(v, u);
    }
}

void Build(int n, int m, int A[], int B[]) {
    for(int i = 0; i < m; ++i) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    memset(comp, -1, sizeof comp); 

    gen(0);
    mark(0);
    dfs(0);
}  


void Joi(int n, int m, int A[], int B[], long long X, int T) {
    Build(n, m, A, B);

    for(int i = 0; i < n; ++i) {
        MessageBoard(i, X >> bit[i] & 1);
    }
}

Ioi

#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;

using namespace std;

static const int N = 10010;
static const int B = 60;

static vector<int> adj[N], g[N]; 
static bitset<N> st[N]; 
static int vis[N], bit[N], p[N], comp[N], cnt, idx, deg[N]; 

void gen(int u) {
    vis[u] = 1; 
    for(int v : g[u]) if(!vis[v]) {
        adj[u].push_back(v); 
        adj[v].push_back(u);
        p[v] = u; 
        gen(v); 
    }
}

void mark(int u, int par = -1) {
    ++cnt; 
    st[0][u] = 1; 
    comp[u] = 0;
    bit[u] = cnt - 1;

    for(int v : adj[u]) if(v != par) {
        if(cnt < B) mark(v, u); 
        else break; 
    }
}

void dfs(int u, int par = -1) {
    int leaf = -1; 

    bitset<N> &S = st[comp[u]]; 
    vector<int> nodes;

    for(int i = S._Find_first(); i < S.size(); i = S._Find_next(i)) 
        deg[i] = 0, nodes.push_back(i); 

    for(int v : nodes) {
        if(!v) continue;
        if(S[p[v]]) {
            ++deg[p[v]]; 
            ++deg[v];
        }
    }

    for(int v : nodes) {
        if(deg[v] == 1 && v != u) {
            leaf = v; break; 
        }
    }

    for(int v : adj[u]) if(v != par) {
        if(comp[v] == -1) {
            comp[v] = ++idx;
            st[idx] = st[comp[u]]; 
            bit[v] = bit[leaf]; 
            st[idx][leaf] = 0; 
            st[idx][v] = 1; 
        } dfs(v, u);
    }
}

void Build(int n, int m, int A[], int B[]) {
    for(int i = 0; i < m; ++i) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    memset(comp, -1, sizeof comp); 

    gen(0);
    mark(0);
    dfs(0);
}  

long long number, c; 

void visit(int u, long long x, int par = -1) {
    number |= x << bit[u];
    for(int v : adj[u]) if(v != par && st[c][v]) {
        visit(v, Move(v), u); 
    }
    if(par + 1) Move(par);
}

long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
    Build(n, m, A, B);

    c = comp[P]; 
    visit(P, V);
    return number;
}

Compilation message (stderr)

Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:41:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = S._Find_first(); i < S.size(); i = S._Find_next(i)) 
                                  ~~^~~~~~~~~~

Ioi.cpp: In function 'void dfs(int, int)':
Ioi.cpp:42:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = S._Find_first(); i < S.size(); i = S._Find_next(i)) 
                                  ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17