Submission #100753

#	Time	Username	Problem	Language	Result	Execution time	Memory
100753		dlalswp25	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	67 ms	9500 KiB

Joi

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

using namespace std;

vector<int> G[10101];
vector<int> adj[10101];
bool vst[10101];

int C[10101];
int W[10101];
int cid;
vector<int> tre[10101];
int cnt;

void init(int x) {
    vst[x] = true;
    for(int i : G[x]) {
        if(vst[i]) continue;
        adj[x].push_back(i);
        adj[i].push_back(x);
        init(i);
    }
}

void dfs(int x, int p) {
    cnt++;
    tre[cid].push_back(x);
    C[x] = cid;
    for(int i : adj[x]) {
        if(cnt >= 60) break;
        if(i == p) continue;
        dfs(i, x);
    }
}

void dfs2(int x, int p, int c) {
    tre[cid].push_back(x);
    cnt++;
    for(int i : adj[x]) {
        if(cnt >= 60) break;
        if(C[i] != c) continue;
        if(i == p) continue;
        dfs2(i, x, c);
    }
}

void mk(int x, int p) {
    cid++;
    cnt = 0;
    dfs(x, p);
    if(tre[cid].size() < 60) {
        dfs2(p, -1, C[p]);
    }
}

void sol(int x, int p) {
    if(!C[x]) mk(x, p);
    for(int i : adj[x]) {
        if(i != p) sol(i, x);
    }
}

bool used[66];

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    for(int i = 0; i < N; i++) W[i] = 60;
    for(int i = 0; i < M; i++) {
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }
    init(0);
    sol(0, -1);
    
    for(int i = 1; i <= cid; i++) {
        for(int j = 0; j < 60; j++) used[j] = false;
        for(int j : tre[i]) used[W[j]] = true;
        int p = 0;
        for(int j : tre[i]) {
            if(W[j] < 60) continue;
            while(used[p]) p++;
            W[j] = p;
            used[p] = true;
        }
    }
    for(int i = 0; i < N; i++) MessageBoard(i, (X & ((1ll) << W[i])) > 0);
}

Ioi

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

using namespace std;

struct XX {

vector<int> G[10101];
vector<int> adj[10101];
bool vst[10101];

int C[10101];
int W[10101];
int cid;
vector<int> tre[10101];
int cnt;

void init(int x) {
    vst[x] = true;
    for(int i : G[x]) {
        if(vst[i]) continue;
        adj[x].push_back(i);
        adj[i].push_back(x);
        init(i);
    }
}

void dfs(int x, int p) {
    cnt++;
    tre[cid].push_back(x);
    C[x] = cid;
    for(int i : adj[x]) {
        if(cnt >= 60) break;
        if(i == p) continue;
        dfs(i, x);
    }
}

void dfs2(int x, int p, int c) {
    tre[cid].push_back(x);
    cnt++;
    for(int i : adj[x]) {
        if(cnt >= 60) break;
        if(C[i] != c) continue;
        if(i == p) continue;
        dfs2(i, x, c);
    }
}

void mk(int x, int p) {
    cid++;
    cnt = 0;
    dfs(x, p);
    if(tre[cid].size() < 60) {
        dfs2(p, -1, C[p]);
    }
}

void sol(int x, int p) {
    if(!C[x]) mk(x, p);
    for(int i : adj[x]) {
        if(i != p) sol(i, x);
    }
}

bool used[66];

}XXX;

int ans[66];
int c;

void trav(int x, int p) {
    for(int i : XXX.adj[x]) {
        if(i == p) continue;
        bool ok = false;
        for(int j : XXX.tre[c]) if(j == i) ok = true;
        if(!ok) continue;
        ans[XXX.W[i]] = Move(i);
        trav(i, x);
    }
    if(p != -1) Move(p);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    for(int i = 0; i < N; i++) XXX.W[i] = 60;
    for(int i = 0; i < M; i++) {
        XXX.G[A[i]].push_back(B[i]);
        XXX.G[B[i]].push_back(A[i]);
    }
    XXX.cid = 0;
    XXX.init(0);
    XXX.sol(0, -1);
    
    for(int i = 1; i <= XXX.cid; i++) {
        for(int j = 0; j < 60; j++) XXX.used[j] = false;
        for(int j : XXX.tre[i]) XXX.used[XXX.W[j]] = true;
        int p = 0;
        for(int j : XXX.tre[i]) {
            if(XXX.W[j] < 60) continue;
            while(XXX.used[p]) p++;
            XXX.W[j] = p;
            XXX.used[p] = true;
        }
    }
    
    ans[XXX.W[P]] = V;
    c = XXX.C[P];
    trav(P, -1);
           
    long long ret = 0;
    for(int i = 0; i < 60; i++) if(ans[i]) ret += ((1ll) << i);
    
    return ret;
}

Compilation message (stderr)

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:55:13: warning: array subscript is below array bounds [-Warray-bounds]
         dfs2(p, -1, C[p]);
         ~~~~^~~~~~~~~~~~~

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