oj.uz

Submission #128230

# Submission time Handle Problem Language Result Execution time Memory
128230 2019-07-10T14:47:16 Z arnold518 Amusement Park (JOI17_amusement_park) C++14
18 / 100
 3000 ms 58040 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 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);
    }
}

#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3452 KB Output is correct
2 Correct 10 ms 3948 KB Output is correct
3 Correct 14 ms 4612 KB Output is correct
4 Correct 12 ms 3816 KB Output is correct
5 Correct 8 ms 3616 KB Output is correct
6 Correct 10 ms 3956 KB Output is correct
7 Correct 16 ms 4612 KB Output is correct
8 Correct 16 ms 4604 KB Output is correct
9 Correct 13 ms 4548 KB Output is correct
10 Correct 10 ms 3708 KB Output is correct
11 Correct 13 ms 4080 KB Output is correct
12 Correct 7 ms 3324 KB Output is correct
13 Correct 15 ms 4464 KB Output is correct
14 Correct 14 ms 4612 KB Output is correct
15 Correct 14 ms 4604 KB Output is correct
16 Correct 14 ms 4604 KB Output is correct
17 Correct 14 ms 4740 KB Output is correct
18 Correct 14 ms 4476 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 58040 KB Output is correct
2 Correct 397 ms 57820 KB Output is correct
3 Correct 369 ms 58020 KB Output is correct
4 Correct 330 ms 56096 KB Output is correct
5 Correct 324 ms 57096 KB Output is correct
6 Correct 365 ms 56672 KB Output is correct
7 Correct 389 ms 56604 KB Output is correct
8 Correct 386 ms 56864 KB Output is correct
9 Correct 374 ms 56848 KB Output is correct
10 Execution timed out 3856 ms 56264 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 3444 KB Output is correct
2 Correct 9 ms 3464 KB Output is correct
3 Correct 9 ms 3528 KB Output is correct
4 Correct 51 ms 12016 KB Output is correct
5 Correct 47 ms 11708 KB Output is correct
6 Correct 46 ms 11820 KB Output is correct
7 Correct 46 ms 11908 KB Output is correct
8 Correct 48 ms 11804 KB Output is correct
9 Correct 250 ms 56764 KB Output is correct
10 Correct 231 ms 56608 KB Output is correct
11 Correct 231 ms 56644 KB Output is correct
12 Correct 7 ms 3536 KB Output is correct
13 Correct 8 ms 3516 KB Output is correct
14 Correct 7 ms 3436 KB Output is correct
15 Correct 7 ms 3416 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 57988 KB Output is correct
2 Correct 334 ms 57728 KB Output is correct
3 Correct 338 ms 57856 KB Output is correct
4 Correct 313 ms 56400 KB Output is correct
5 Correct 308 ms 56992 KB Output is correct
6 Correct 343 ms 56576 KB Output is correct
7 Correct 340 ms 56728 KB Output is correct
8 Correct 344 ms 56712 KB Output is correct
9 Correct 340 ms 56608 KB Output is correct
10 Execution timed out 3856 ms 56056 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 57980 KB Output is correct
2 Correct 333 ms 57600 KB Output is correct
3 Correct 333 ms 57600 KB Output is correct
4 Correct 318 ms 56336 KB Output is correct
5 Correct 324 ms 57248 KB Output is correct
6 Correct 380 ms 56476 KB Output is correct
7 Correct 360 ms 56864 KB Output is correct
8 Correct 335 ms 56600 KB Output is correct
9 Correct 336 ms 56524 KB Output is correct
10 Execution timed out 3819 ms 56400 KB Time limit exceeded
11 Halted 0 ms 0 KB -