Submission #128230

#	Time	Username	Problem	Language	Result	Execution time	Memory
128230		arnold518	Amusement Park (JOI17_amusement_park)	C++14	18 / 100	3856 ms	58040 KiB

Joi

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e4;

static int N, M;
static ll X;

static vector<int> adj[MAXN+10], tree[MAXN+10];
static unordered_set<int> group[MAXN+10];
static int dis[MAXN+10], invdis[MAXN+10], par[MAXN+10], col[MAXN+10];

static int cnt=0;
static void makeTree(int now)
{
    int i, j;
    dis[now]=cnt++;
    invdis[dis[now]]=now;
    if(dis[now]<60)
    {
        group[now].insert(now);
        col[now]=dis[now];
    }

    for(int nxt : adj[now])
    {
        if(dis[nxt]!=-1) continue;
        makeTree(nxt);
        tree[now].push_back(nxt);
        tree[nxt].push_back(now);
        par[nxt]=now;
    }
}

static int leaf;
static bool dfs(int now, int bef, int grp, int grpnow)
{
    if(cnt==60) { leaf=now; return 1; }
    cnt++;
    group[grpnow].insert(now);
    for(int nxt : tree[now])
    {
        if(nxt==bef) continue;
        if(!group[grp].count(nxt)) continue;
        if(dfs(nxt, now, grp, grpnow)) return 1;
    }
    return 0;
}

static void color()
{
    int i, j;
    unordered_set<int> start;
    for(i=0; i<N; i++) if(dis[i]<60) start.insert(*group[i].begin());
    for(i=0; i<N; i++) if(dis[i]<60) group[i]=start;

    int sum=0;
    for(i=60; i<N; i++)
    {
        int now=invdis[i];
        cnt=1; leaf=0;
        dfs(par[now], now, par[now], now);
        col[now]=col[leaf];
        group[now].insert(now);
        sum+=cnt;
    }
    //printf("%d\n", sum);
}

void Joi(int n, int m, int A[], int B[], ll x, int T)
{
    int i, j;
    N=n; M=m; X=x;

    for(i=0; i<M; i++)
    {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }

    //printf("CHECKPOINT1\n");
    memset(dis, -1, sizeof(dis));
    memset(col, -1, sizeof(col));
    makeTree(1);
    //printf("CHECKPOINT2\n");
    color();
    //printf("CHECKPOINT3\n");
    for(i=0; i<N; i++)
    {
        if(x&(1ll<<col[i])) MessageBoard(i, 1);
        else MessageBoard(i, 0);
    }
}

Ioi

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e4;

static int N, M, P, V;

static vector<int> adj[MAXN+10], tree[MAXN+10];
static unordered_set<int> group[MAXN+10];
static int dis[MAXN+10], invdis[MAXN+10], par[MAXN+10], col[MAXN+10], chk[MAXN+10];
static ll ans;

static int cnt=0;
static void makeTree(int now)
{
    int i, j;
    dis[now]=cnt++;
    invdis[dis[now]]=now;
    if(dis[now]<60)
    {
        group[now].insert(now);
        col[now]=dis[now];
    }

    for(int nxt : adj[now])
    {
        if(dis[nxt]!=-1) continue;
        makeTree(nxt);
        tree[now].push_back(nxt);
        tree[nxt].push_back(now);
        par[nxt]=now;
    }
}

static int leaf;
static bool dfs(int now, int bef, int grp, int grpnow)
{
    if(cnt==60) { leaf=now; return 1; }
    cnt++;
    group[grpnow].insert(now);
    for(int nxt : tree[now])
    {
        if(nxt==bef) continue;
        if(!group[grp].count(nxt)) continue;
        if(dfs(nxt, now, grp, grpnow)) return 1;
    }
    return 0;
}

static void color()
{
    int i, j;
    unordered_set<int> start;
    for(i=0; i<N; i++) if(dis[i]<60) start.insert(*group[i].begin());
    for(i=0; i<N; i++) if(dis[i]<60) group[i]=start;

    int sum=0;
    for(i=60; i<N; i++)
    {
        int now=invdis[i];
        cnt=1; leaf=0;
        dfs(par[now], now, par[now], now);
        col[now]=col[leaf];
        group[now].insert(now);
        sum+=cnt;
    }
    //printf("%d\n", sum);
}

static void tour(int now, int bef)
{
    for(int nxt : tree[now])
    {
        if(nxt==bef) continue;
        if(!chk[nxt]) continue;
        ans|=(ll)Move(nxt)<<col[nxt];
        tour(nxt, now);
        ans|=(ll)Move(now)<<col[now];
    }
}

ll Ioi(int n, int m, int A[], int B[], int p, int v, int T)
{
    int i, j;
    N=n; M=m; P=p; V=v;

    for(i=0; i<M; i++)
    {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }

    memset(dis, -1, sizeof(dis));
    memset(col, -1, sizeof(col));
    makeTree(1);
    color();

    for(auto it : group[P]) chk[it]=1;

    ans|=(ll)V<<col[P];
    tour(P, P);
    return ans;
}

Compilation message (stderr)

Joi.cpp: In function 'void makeTree(int)':
Joi.cpp:21:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
Joi.cpp:21:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
Joi.cpp: In function 'void color()':
Joi.cpp:57:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
Joi.cpp: In function 'void Joi(int, int, int*, int*, ll, int)':
Joi.cpp:77:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Ioi.cpp: In function 'void makeTree(int)':
Ioi.cpp:21:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
Ioi.cpp:21:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
Ioi.cpp: In function 'void color()':
Ioi.cpp:57:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:89:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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