oj.uz

Submission #154533

# Submission time Handle Problem Language Result Execution time Memory
154533 2019-09-22T14:40:11 Z Mercenary Amusement Park (JOI17_amusement_park) C++14
100 / 100
 33 ms 5332 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    const static int maxn = 1e4 + 5;
    static int lab[maxn];
    static int nTime = 0;
    static int id[maxn];
    static long long res = 0;
    static long long cal = 0;
    static vector<int> adj[maxn];
    fill_n(lab,maxn,-1);
    function<int(int)> FindLab = [&](int u){
        return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
    };
    for(int i = 0 ; i < M ; ++i){
        int s = FindLab(A[i]);
        int d = FindLab(B[i]);
        if(s != d){
            if(lab[s] > lab[d])swap(s , d);
            lab[s] += lab[d];
            lab[d] = s;
            adj[A[i]].push_back(B[i]);
            adj[B[i]].push_back(A[i]);
        }
    }
    function<void(int,int)> DFS = [&](int u , int par){
        id[u] = nTime;
        ++nTime;
        nTime %= 60;
        for(int c : adj[u]){
            if(c != par){
                DFS(c , u);
            }
        }
    };
    DFS(0 , -1);
    for(int i = 0 ; i < N ; ++i){
        MessageBoard(i , (X >> id[i]) & 1);
    }
}


#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    const static int maxn = 1e4 + 5;
    static int lab[maxn];
    static int nTime = 0;
    static int id[maxn];
    static long long res = 0;
    static long long cal = 0;
    static int sub[maxn] , h[maxn];
    static long long can[maxn];
    static int p[maxn];
    static vector<int> adj[maxn];
    static vector<int> child[maxn];
    fill_n(lab,maxn,-1);
    function<int(int)> FindLab = [&](int u){
        return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
    };
    for(int i = 0 ; i < M ; ++i){
        int s = FindLab(A[i]);
        int d = FindLab(B[i]);
        if(s != d){
            if(lab[s] > lab[d])swap(s , d);
            lab[s] += lab[d];
            lab[d] = s;
            adj[A[i]].push_back(B[i]);
            adj[B[i]].push_back(A[i]);
        }
    }
    function<void(int,int)> DFS = [&](int u , int par){
        id[u] = nTime;
        ++nTime;
        nTime %= 60;
        sub[u] = 1;
        for(int c : adj[u]){
            if(c != par){
                child[u].push_back(c);
                p[c] = u;
                DFS(c , u);
                sub[u] += sub[c];
            }
        }
    };
    int lim = 60;
    function<void(int,int)> DFS3 = [&](int u , int par){
        lim--;
        h[u] = -1e9;
        if(lim < 0)return;
        can[u] = (1ll << id[u]);
        sub[u] = 1;
        for(int c : child[u]){
            if(c != par){
                p[c] = u;
                DFS3(c , u);
                h[u] = max(h[u] , h[c] + 1);
                can[u] |= can[c];
            }
        }
    };
    function<void(int)> DFS2 = [&](int u){
        cal |= (1ll << id[u]);
        if(V)res |= (1ll << id[u]);
        for(int c : child[u]){
            if(__builtin_popcountll(cal) == 60)return;
            if((~cal) & can[c]){
                V = Move(c);
                DFS2(c);
                V = Move(u);
            }
        }
    };
    function<void(int)> DFS1 = [&](int u){
        cal |= (1ll << id[u]);
        if(V)res |= (1ll << id[u]);
        if(child[u].empty())return;
        int best = -1;
        for(int c : child[u]){
            if(__builtin_popcountll(cal) == 60)return;
            if((~cal) & can[c]){
                if(best == -1 || h[best] < h[c])best = c;
            }
        }
        for(int c : child[u]){
            if(__builtin_popcountll(cal) == 60)return;
            if(c == best)continue;
            if((~cal) & can[c]){
                V = Move(c);
                DFS2(c);
                V = Move(u);
            }
        }
        if(best != -1 && ((~cal) & can[best])){
            V = Move(best);
            DFS1(best);
        }
    };
    DFS(0 , -1);
    while(sub[P] < 60){
        cal |= (1ll << id[P]);
        if(V)res |= (1ll << id[P]);
        V = Move(p[P]);
        P = p[P];
    }
    DFS3(P , -1);
    DFS1(P);
//    cout << bitset<60>(cal);
    return res;
}

Compilation message

Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:10:22: warning: unused variable 'res' [-Wunused-variable]
     static long long res = 0;
                      ^~~
Joi.cpp:11:22: warning: unused variable 'cal' [-Wunused-variable]
     static long long cal = 0;
                      ^~~
Joi.cpp: At global scope:
Joi.cpp:11:22: warning: 'cal' defined but not used [-Wunused-variable]
Joi.cpp:10:22: warning: 'res' defined but not used [-Wunused-variable]
     static long long res = 0;
                      ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1648 KB Output is correct
2 Correct 5 ms 1648 KB Output is correct
3 Correct 6 ms 1660 KB Output is correct
4 Correct 5 ms 1592 KB Output is correct
5 Correct 4 ms 1652 KB Output is correct
6 Correct 6 ms 1664 KB Output is correct
7 Correct 6 ms 1668 KB Output is correct
8 Correct 5 ms 1668 KB Output is correct
9 Correct 6 ms 1708 KB Output is correct
10 Correct 4 ms 1660 KB Output is correct
11 Correct 8 ms 1856 KB Output is correct
12 Correct 5 ms 1532 KB Output is correct
13 Correct 6 ms 1660 KB Output is correct
14 Correct 6 ms 1668 KB Output is correct
15 Correct 5 ms 1724 KB Output is correct
16 Correct 6 ms 1668 KB Output is correct
17 Correct 6 ms 1668 KB Output is correct
18 Correct 6 ms 1704 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4104 KB Output is correct
2 Correct 31 ms 4100 KB Output is correct
3 Correct 31 ms 4032 KB Output is correct
4 Correct 22 ms 3384 KB Output is correct
5 Correct 23 ms 4416 KB Output is correct
6 Correct 22 ms 3904 KB Output is correct
7 Correct 22 ms 4248 KB Output is correct
8 Correct 22 ms 4232 KB Output is correct
9 Correct 23 ms 4632 KB Output is correct
10 Correct 19 ms 3848 KB Output is correct
11 Correct 19 ms 3696 KB Output is correct
12 Correct 20 ms 3352 KB Output is correct
13 Correct 20 ms 3528 KB Output is correct
14 Correct 20 ms 3508 KB Output is correct
15 Correct 22 ms 3608 KB Output is correct
16 Correct 22 ms 3872 KB Output is correct
17 Correct 22 ms 3612 KB Output is correct
18 Correct 22 ms 3852 KB Output is correct
19 Correct 22 ms 3628 KB Output is correct
20 Correct 18 ms 4248 KB Output is correct
21 Correct 18 ms 4336 KB Output is correct
22 Correct 22 ms 3996 KB Output is correct
23 Correct 23 ms 4272 KB Output is correct
24 Correct 22 ms 4256 KB Output is correct
25 Correct 23 ms 4256 KB Output is correct
26 Correct 23 ms 4152 KB Output is correct
27 Correct 22 ms 4288 KB Output is correct
28 Correct 23 ms 4496 KB Output is correct
29 Correct 20 ms 4104 KB Output is correct
30 Correct 22 ms 4244 KB Output is correct
31 Correct 6 ms 1652 KB Output is correct
32 Correct 5 ms 1524 KB Output is correct
33 Correct 6 ms 1640 KB Output is correct
34 Correct 6 ms 1648 KB Output is correct
35 Correct 6 ms 1660 KB Output is correct
36 Correct 5 ms 1708 KB Output is correct
37 Correct 4 ms 1652 KB Output is correct
38 Correct 5 ms 1712 KB Output is correct
39 Correct 4 ms 1524 KB Output is correct
40 Correct 6 ms 1652 KB Output is correct
41 Correct 4 ms 1652 KB Output is correct
42 Correct 5 ms 1652 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1656 KB Output is correct
2 Correct 5 ms 1652 KB Output is correct
3 Correct 4 ms 1652 KB Output is correct
4 Correct 6 ms 2208 KB Output is correct
5 Correct 7 ms 2212 KB Output is correct
6 Correct 8 ms 2208 KB Output is correct
7 Correct 8 ms 2208 KB Output is correct
8 Correct 8 ms 2208 KB Output is correct
9 Correct 18 ms 5332 KB Output is correct
10 Correct 18 ms 5280 KB Output is correct
11 Correct 18 ms 5272 KB Output is correct
12 Correct 4 ms 1552 KB Output is correct
13 Correct 5 ms 1556 KB Output is correct
14 Correct 5 ms 1748 KB Output is correct
15 Correct 5 ms 1524 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4224 KB Output is correct
2 Correct 31 ms 4400 KB Output is correct
3 Correct 32 ms 4336 KB Output is correct
4 Correct 22 ms 3612 KB Output is correct
5 Correct 22 ms 4888 KB Output is correct
6 Correct 22 ms 4276 KB Output is correct
7 Correct 23 ms 4248 KB Output is correct
8 Correct 22 ms 4128 KB Output is correct
9 Correct 22 ms 4120 KB Output is correct
10 Correct 20 ms 3748 KB Output is correct
11 Correct 20 ms 3608 KB Output is correct
12 Correct 20 ms 3464 KB Output is correct
13 Correct 20 ms 3740 KB Output is correct
14 Correct 22 ms 3468 KB Output is correct
15 Correct 22 ms 3608 KB Output is correct
16 Correct 22 ms 3736 KB Output is correct
17 Correct 23 ms 3712 KB Output is correct
18 Correct 22 ms 3480 KB Output is correct
19 Correct 23 ms 3716 KB Output is correct
20 Correct 18 ms 4452 KB Output is correct
21 Correct 18 ms 4384 KB Output is correct
22 Correct 23 ms 4248 KB Output is correct
23 Correct 22 ms 4120 KB Output is correct
24 Correct 22 ms 4120 KB Output is correct
25 Correct 23 ms 4300 KB Output is correct
26 Correct 23 ms 4120 KB Output is correct
27 Correct 22 ms 4376 KB Output is correct
28 Correct 15 ms 3992 KB Output is correct
29 Correct 20 ms 4096 KB Output is correct
30 Correct 22 ms 4096 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4352 KB Output is correct
2 Correct 32 ms 4224 KB Output is correct
3 Correct 33 ms 4352 KB Output is correct
4 Correct 22 ms 3608 KB Output is correct
5 Correct 23 ms 5172 KB Output is correct
6 Correct 23 ms 4248 KB Output is correct
7 Correct 22 ms 4120 KB Output is correct
8 Correct 19 ms 4248 KB Output is correct
9 Correct 22 ms 4124 KB Output is correct
10 Correct 20 ms 3740 KB Output is correct
11 Correct 20 ms 3720 KB Output is correct
12 Correct 20 ms 3584 KB Output is correct
13 Correct 20 ms 3328 KB Output is correct
14 Correct 20 ms 3764 KB Output is correct
15 Correct 22 ms 3608 KB Output is correct
16 Correct 22 ms 3736 KB Output is correct
17 Correct 22 ms 3740 KB Output is correct
18 Correct 22 ms 3492 KB Output is correct
19 Correct 22 ms 3480 KB Output is correct
20 Correct 18 ms 4376 KB Output is correct
21 Correct 18 ms 4376 KB Output is correct
22 Correct 22 ms 4248 KB Output is correct
23 Correct 22 ms 4256 KB Output is correct
24 Correct 22 ms 4420 KB Output is correct
25 Correct 22 ms 4120 KB Output is correct
26 Correct 22 ms 3992 KB Output is correct
27 Correct 22 ms 4384 KB Output is correct
28 Correct 22 ms 4376 KB Output is correct
29 Correct 20 ms 4104 KB Output is correct
30 Correct 22 ms 4236 KB Output is correct
31 Correct 5 ms 1532 KB Output is correct
32 Correct 6 ms 1572 KB Output is correct
33 Correct 6 ms 1976 KB Output is correct
34 Correct 6 ms 1688 KB Output is correct
35 Correct 5 ms 1792 KB Output is correct
36 Correct 5 ms 1524 KB Output is correct
37 Correct 6 ms 1916 KB Output is correct
38 Correct 5 ms 1944 KB Output is correct
39 Correct 5 ms 1524 KB Output is correct
40 Correct 6 ms 2168 KB Output is correct
41 Correct 5 ms 1788 KB Output is correct
42 Correct 6 ms 1692 KB Output is correct