oj.uz

Submission #128123

# Submission time Handle Problem Language Result Execution time Memory
128123 2019-07-10T12:46:35 Z arnold518 Amusement Park (JOI17_amusement_park) C++14
18 / 100
 3000 ms 57584 KB 
#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 void dfs(int now, int bef, int grp)
{
    if(cnt==60) { leaf=now; return; }
    cnt++;
    for(int nxt : tree[now])
    {
        if(cnt==61) return;
        if(nxt==bef) continue;
        if(!group[grp].count(nxt)) continue;
        dfs(nxt, now, grp);
    }
}

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;

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

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);
    }
}

#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 void dfs(int now, int bef, int grp)
{
    if(cnt==60) { leaf=now; return; }
    cnt++;
    for(int nxt : tree[now])
    {
        if(cnt==61) return;
        if(nxt==bef) continue;
        if(!group[grp].count(nxt)) continue;
        dfs(nxt, now, grp);
    }
}

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;

    for(i=60; i<N; i++)
    {
        int now=invdis[i];
        cnt=1; leaf=0;
        dfs(par[now], now, par[now]);
        for(int it : group[par[now]]) if(it!=leaf) group[now].insert(it);
        col[now]=col[leaf];
        group[now].insert(now);
    }
}

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

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:56:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
Joi.cpp: In function 'void Joi(int, int, int*, int*, ll, int)':
Joi.cpp:75: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:56: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:86:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3440 KB Output is correct
2 Correct 11 ms 3828 KB Output is correct
3 Correct 13 ms 4608 KB Output is correct
4 Correct 8 ms 3440 KB Output is correct
5 Correct 8 ms 3568 KB Output is correct
6 Correct 10 ms 3824 KB Output is correct
7 Correct 14 ms 4472 KB Output is correct
8 Correct 14 ms 4600 KB Output is correct
9 Correct 12 ms 4472 KB Output is correct
10 Correct 8 ms 3696 KB Output is correct
11 Correct 12 ms 3876 KB Output is correct
12 Correct 6 ms 3184 KB Output is correct
13 Correct 13 ms 4600 KB Output is correct
14 Correct 14 ms 4608 KB Output is correct
15 Correct 14 ms 4604 KB Output is correct
16 Correct 14 ms 4684 KB Output is correct
17 Correct 14 ms 4472 KB Output is correct
18 Correct 16 ms 4684 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 57384 KB Output is correct
2 Correct 334 ms 57340 KB Output is correct
3 Correct 337 ms 57480 KB Output is correct
4 Correct 341 ms 56068 KB Output is correct
5 Correct 310 ms 56772 KB Output is correct
6 Correct 337 ms 56420 KB Output is correct
7 Correct 341 ms 56296 KB Output is correct
8 Correct 341 ms 56408 KB Output is correct
9 Correct 348 ms 56508 KB Output is correct
10 Execution timed out 3029 ms 27576 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3440 KB Output is correct
2 Correct 8 ms 3440 KB Output is correct
3 Correct 8 ms 3444 KB Output is correct
4 Correct 45 ms 11676 KB Output is correct
5 Correct 44 ms 11776 KB Output is correct
6 Correct 44 ms 11672 KB Output is correct
7 Correct 44 ms 11724 KB Output is correct
8 Correct 48 ms 11724 KB Output is correct
9 Correct 241 ms 56376 KB Output is correct
10 Correct 240 ms 56376 KB Output is correct
11 Correct 239 ms 56504 KB Output is correct
12 Correct 6 ms 3568 KB Output is correct
13 Correct 8 ms 3420 KB Output is correct
14 Correct 6 ms 3312 KB Output is correct
15 Correct 6 ms 3312 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 57584 KB Output is correct
2 Correct 337 ms 57404 KB Output is correct
3 Correct 333 ms 57152 KB Output is correct
4 Correct 316 ms 56024 KB Output is correct
5 Correct 334 ms 56716 KB Output is correct
6 Correct 380 ms 56532 KB Output is correct
7 Correct 340 ms 56280 KB Output is correct
8 Correct 343 ms 56504 KB Output is correct
9 Correct 343 ms 56488 KB Output is correct
10 Execution timed out 3014 ms 27352 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 57320 KB Output is correct
2 Correct 332 ms 57372 KB Output is correct
3 Correct 334 ms 57404 KB Output is correct
4 Correct 315 ms 55948 KB Output is correct
5 Correct 321 ms 56996 KB Output is correct
6 Correct 345 ms 56500 KB Output is correct
7 Correct 397 ms 56504 KB Output is correct
8 Correct 335 ms 56560 KB Output is correct
9 Correct 343 ms 56716 KB Output is correct
10 Execution timed out 3030 ms 27496 KB Time limit exceeded
11 Halted 0 ms 0 KB -