oj.uz

Submission #154529

# Submission time Handle Problem Language Result Execution time Memory
154529 2019-09-22T14:01:26 Z Mercenary Amusement Park (JOI17_amusement_park) C++14
82 / 100
 34 ms 5412 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){
            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;
        can[u] = (1ll << 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);
                h[u] = max(h[u] , h[c] + 1);
                sub[u] += sub[c];
                can[u] |= can[c];
            }
        }
        if(u == P)h[u] = -1e9;
    };
    DFS(0 , -1);
    function<void(int)> DFS2 = [&](int u){
        cal |= (1ll << id[u]);
//        cout << id[u] << " " << cal << endl;
        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);
        }
    };
    DFS2(P);
    while(sub[P] < 60){
        cal |= (1ll << id[P]);
        if(V)res |= (1ll << id[P]);
        V = Move(p[P]);
        P = p[P];
    }
    DFS1(P);
    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 5 ms 1660 KB Output is correct
2 Correct 6 ms 1660 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 5 ms 1652 KB Output is correct
5 Correct 6 ms 1652 KB Output is correct
6 Correct 5 ms 1740 KB Output is correct
7 Correct 6 ms 1668 KB Output is correct
8 Correct 6 ms 1668 KB Output is correct
9 Correct 5 ms 1532 KB Output is correct
10 Correct 5 ms 1532 KB Output is correct
11 Correct 9 ms 1856 KB Output is correct
12 Correct 6 ms 1524 KB Output is correct
13 Correct 6 ms 1660 KB Output is correct
14 Correct 6 ms 1544 KB Output is correct
15 Correct 6 ms 1532 KB Output is correct
16 Correct 5 ms 1700 KB Output is correct
17 Correct 6 ms 1660 KB Output is correct
18 Correct 6 ms 1728 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4228 KB Output is correct
2 Correct 31 ms 4492 KB Output is correct
3 Correct 31 ms 4380 KB Output is correct
4 Correct 22 ms 3480 KB Output is correct
5 Correct 23 ms 4512 KB Output is correct
6 Correct 22 ms 4248 KB Output is correct
7 Correct 22 ms 4248 KB Output is correct
8 Correct 23 ms 4256 KB Output is correct
9 Correct 22 ms 4248 KB Output is correct
10 Correct 19 ms 3812 KB Output is correct
11 Correct 19 ms 3612 KB Output is correct
12 Correct 20 ms 3464 KB Output is correct
13 Correct 20 ms 3328 KB Output is correct
14 Correct 20 ms 3596 KB Output is correct
15 Correct 22 ms 3576 KB Output is correct
16 Correct 22 ms 3608 KB Output is correct
17 Correct 22 ms 3616 KB Output is correct
18 Correct 22 ms 3720 KB Output is correct
19 Correct 22 ms 3624 KB Output is correct
20 Correct 18 ms 4608 KB Output is correct
21 Correct 18 ms 4384 KB Output is correct
22 Correct 22 ms 4120 KB Output is correct
23 Correct 23 ms 4248 KB Output is correct
24 Correct 22 ms 4112 KB Output is correct
25 Correct 22 ms 4504 KB Output is correct
26 Correct 22 ms 4256 KB Output is correct
27 Correct 23 ms 4248 KB Output is correct
28 Correct 22 ms 4376 KB Output is correct
29 Correct 20 ms 3840 KB Output is correct
30 Correct 22 ms 4196 KB Output is correct
31 Correct 5 ms 1524 KB Output is correct
32 Correct 5 ms 1652 KB Output is correct
33 Correct 5 ms 1668 KB Output is correct
34 Correct 5 ms 1688 KB Output is correct
35 Correct 6 ms 1524 KB Output is correct
36 Correct 4 ms 1652 KB Output is correct
37 Correct 6 ms 1652 KB Output is correct
38 Correct 6 ms 1532 KB Output is correct
39 Correct 5 ms 1756 KB Output is correct
40 Correct 5 ms 1660 KB Output is correct
41 Correct 6 ms 1652 KB Output is correct
42 Correct 4 ms 1656 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1660 KB Output is correct
2 Correct 6 ms 1660 KB Output is correct
3 Correct 5 ms 1616 KB Output is correct
4 Correct 6 ms 2296 KB Output is correct
5 Correct 7 ms 2208 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 2336 KB Output is correct
9 Correct 19 ms 5272 KB Output is correct
10 Correct 19 ms 5412 KB Output is correct
11 Correct 20 ms 5412 KB Output is correct
12 Correct 6 ms 1524 KB Output is correct
13 Correct 4 ms 1524 KB Output is correct
14 Correct 6 ms 1652 KB Output is correct
15 Correct 6 ms 1652 KB Output is correct

Subtask #4
54.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4352 KB Output is correct
2 Correct 31 ms 4224 KB Output is correct
3 Correct 31 ms 4224 KB Output is correct
4 Correct 23 ms 3616 KB Output is correct
5 Correct 23 ms 5024 KB Output is correct
6 Correct 22 ms 4256 KB Output is correct
7 Correct 22 ms 4212 KB Output is correct
8 Correct 22 ms 3992 KB Output is correct
9 Correct 22 ms 4256 KB Output is correct
10 Correct 19 ms 3748 KB Output is correct
11 Correct 20 ms 3620 KB Output is correct
12 Correct 20 ms 3456 KB Output is correct
13 Correct 20 ms 3660 KB Output is correct
14 Partially correct 20 ms 3476 KB Partially correct
15 Partially correct 22 ms 3872 KB Partially correct
16 Correct 22 ms 3852 KB Output is correct
17 Correct 22 ms 3720 KB Output is correct
18 Correct 22 ms 3632 KB Output is correct
19 Correct 22 ms 3616 KB Output is correct
20 Correct 18 ms 4512 KB Output is correct
21 Correct 18 ms 4632 KB Output is correct
22 Correct 22 ms 4248 KB Output is correct
23 Correct 22 ms 4200 KB Output is correct
24 Correct 22 ms 4308 KB Output is correct
25 Correct 22 ms 4256 KB Output is correct
26 Correct 22 ms 4224 KB Output is correct
27 Correct 23 ms 4480 KB Output is correct
28 Correct 22 ms 4136 KB Output is correct
29 Correct 22 ms 3840 KB Output is correct
30 Correct 22 ms 4116 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4320 KB Output is correct
2 Correct 32 ms 4352 KB Output is correct
3 Correct 34 ms 4352 KB Output is correct
4 Incorrect 23 ms 3500 KB Output isn't correct
5 Halted 0 ms 0 KB -