oj.uz

Submission #128153

# Submission time Handle Problem Language Result Execution time Memory
128153 2019-07-10T13:15:31 Z arnold518 Amusement Park (JOI17_amusement_park) C++14
18 / 100
 3000 ms 57380 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)
{
    if(cnt==60) { leaf=now; return 1; }
    cnt++;
    for(int nxt : tree[now])
    {
        if(nxt==bef) continue;
        if(!group[grp].count(nxt)) continue;
        if(dfs(nxt, now, grp)) 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]);
        for(int it : group[par[now]]) if(it!=leaf) group[now].insert(it);
        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)
{
    if(cnt==60) { leaf=now; return 1; }
    cnt++;
    for(int nxt : tree[now])
    {
        if(nxt==bef) continue;
        if(!group[grp].count(nxt)) continue;
        if(dfs(nxt, now, grp)) 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;

    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: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: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 7 ms 3312 KB Output is correct
2 Correct 10 ms 4080 KB Output is correct
3 Correct 13 ms 4608 KB Output is correct
4 Correct 8 ms 3684 KB Output is correct
5 Correct 8 ms 3708 KB Output is correct
6 Correct 10 ms 3940 KB Output is correct
7 Correct 14 ms 4736 KB Output is correct
8 Correct 14 ms 4480 KB Output is correct
9 Correct 12 ms 4420 KB Output is correct
10 Correct 8 ms 3720 KB Output is correct
11 Correct 12 ms 4004 KB Output is correct
12 Correct 6 ms 3320 KB Output is correct
13 Correct 13 ms 4608 KB Output is correct
14 Correct 13 ms 4600 KB Output is correct
15 Correct 13 ms 4476 KB Output is correct
16 Correct 13 ms 4496 KB Output is correct
17 Correct 14 ms 4472 KB Output is correct
18 Correct 14 ms 4472 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 57380 KB Output is correct
2 Correct 327 ms 57288 KB Output is correct
3 Correct 330 ms 57272 KB Output is correct
4 Correct 331 ms 56012 KB Output is correct
5 Correct 305 ms 56732 KB Output is correct
6 Correct 329 ms 56424 KB Output is correct
7 Correct 334 ms 56324 KB Output is correct
8 Correct 333 ms 56424 KB Output is correct
9 Correct 329 ms 56660 KB Output is correct
10 Execution timed out 3785 ms 56096 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 3440 KB Output is correct
4 Correct 44 ms 11780 KB Output is correct
5 Correct 47 ms 11740 KB Output is correct
6 Correct 43 ms 11672 KB Output is correct
7 Correct 44 ms 11668 KB Output is correct
8 Correct 43 ms 11672 KB Output is correct
9 Correct 240 ms 56576 KB Output is correct
10 Correct 237 ms 56456 KB Output is correct
11 Correct 244 ms 56632 KB Output is correct
12 Correct 7 ms 3444 KB Output is correct
13 Correct 8 ms 3440 KB Output is correct
14 Correct 9 ms 3312 KB Output is correct
15 Correct 7 ms 3448 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 57224 KB Output is correct
2 Correct 331 ms 57256 KB Output is correct
3 Correct 338 ms 57332 KB Output is correct
4 Correct 312 ms 55808 KB Output is correct
5 Correct 307 ms 56656 KB Output is correct
6 Correct 332 ms 56356 KB Output is correct
7 Correct 334 ms 56436 KB Output is correct
8 Correct 337 ms 56456 KB Output is correct
9 Correct 333 ms 56504 KB Output is correct
10 Execution timed out 3786 ms 56200 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 57264 KB Output is correct
2 Correct 327 ms 57380 KB Output is correct
3 Correct 327 ms 57328 KB Output is correct
4 Correct 311 ms 56088 KB Output is correct
5 Correct 310 ms 57060 KB Output is correct
6 Correct 335 ms 56488 KB Output is correct
7 Correct 332 ms 56404 KB Output is correct
8 Correct 329 ms 56380 KB Output is correct
9 Correct 335 ms 56488 KB Output is correct
10 Execution timed out 3816 ms 56032 KB Time limit exceeded
11 Halted 0 ms 0 KB -