oj.uz

Submission #133866

# Submission time Handle Problem Language Result Execution time Memory
133866 2019-07-21T15:32:15 Z doowey Amusement Park (JOI17_amusement_park) C++14
66 / 100
 69 ms 6436 KB 
#include <bits/stdc++.h>
#include "Joi.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

void send(int idx, int bit){
    MessageBoard(idx, bit);
}

const int N = (int)1e4 + 3;
const int LOG = 60;

vector<int> T[N];

int tin[N]; // modulo LOG
int cnt;

void dfs(int u){
    if(tin[u] != -1){
        return;
    }
    tin[u] = cnt ++ ;
    cnt %= LOG;
    for(auto p : T[u]){
        dfs(p);
    }
}

void Joi(int n, int m, int A[], int B[], ll X, int useless) {
    for(int i = 0 ; i < n; i ++ )
        tin[i] = -1;
    for(int i = 0 ; i < m ; i ++ ){
        T[A[i]].push_back(B[i]);
        T[B[i]].push_back(A[i]);
    }
    dfs(0);
    for(int i = 0 ; i < n; i ++ ){
        if(X & (1ll << tin[i])){
            send(i, 1);
        }
        else{
            send(i, 0);
        }
    }
}

#include <bits/stdc++.h>
#include "Ioi.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());


const int MAXN = (int)1e4 + 9;
const int LG = 60;

vector<int> TT[MAXN];
int ti[MAXN];
int cn;

void gt(int u){
    if(ti[u] != -1) return;
    ti[u] = cn ++ ;
    cn %= LG;
    for(auto p : TT[u]){
        gt(p);
    }
}

int pv[LG][MAXN];

set<int> rem;

int match[LG];

ll Ioi(int n, int m, int a[], int b[], int p, int v, int useless) {
   for(int i = 0 ; i < m ; i ++ ){
        TT[a[i]].push_back(b[i]);
        TT[b[i]].push_back(a[i]);
    }
    for(int i = 0 ; i < n ; i ++ )
        ti[i] = -1;
    gt(0);
    int node;
    for(int i = 0 ; i < LG; i ++ ) {
        for(int j = 0 ; j < n; j ++ )
            pv[i][j] = -1;
        queue<int> ff;
        for(int j = 0 ; j < n; j ++){
            if(ti[j] == i){
                pv[i][j] = j;
                ff.push(j);
            }
        }
        while(!ff.empty()){
            node = ff.front();
            ff.pop();
            for(auto p : TT[node]){
                if(pv[i][p] == -1){
                    pv[i][p] = node;
                    ff.push(p);
                }
            }
        }
    }
    for(int i = 0 ; i < LG; i ++ )
        rem.insert(i);
    rem.erase(ti[p]);
    for(int i = 0 ; i < LG; i ++ )
        match[i] = -1;
    match[ti[p]] = v;
    int go;
    int bit;
    int num;
    while(!rem.empty()){
        num = ((int)rnd() % (int)rem.size() + 71) % (int)rem.size();
        auto it = rem.begin();
        for(int j = 0 ; j < num ; j ++ )
            ++ it;
        go = *it;
        do{
            bit = Move(pv[go][p]);
            p = pv[go][p];  
            if(rem.count(ti[p])){
                rem.erase(ti[p]);
                match[ti[p]] = bit;
            }
        }while(pv[go][p] != p);
    }
    ll ret = 0;
    for(int i = 0 ; i < LG; i ++ )
        ret += match[i] * (1ll << i);
    return ret;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1396 KB Output is correct
2 Correct 4 ms 1656 KB Output is correct
3 Correct 5 ms 1784 KB Output is correct
4 Correct 5 ms 1520 KB Output is correct
5 Correct 4 ms 1392 KB Output is correct
6 Correct 5 ms 1624 KB Output is correct
7 Correct 5 ms 1664 KB Output is correct
8 Correct 5 ms 1768 KB Output is correct
9 Correct 6 ms 1792 KB Output is correct
10 Correct 5 ms 1764 KB Output is correct
11 Correct 9 ms 1840 KB Output is correct
12 Correct 4 ms 1628 KB Output is correct
13 Correct 5 ms 1656 KB Output is correct
14 Correct 5 ms 1664 KB Output is correct
15 Correct 5 ms 1528 KB Output is correct
16 Correct 6 ms 1744 KB Output is correct
17 Correct 6 ms 1656 KB Output is correct
18 Correct 5 ms 1872 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6412 KB Output is correct
2 Correct 68 ms 6344 KB Output is correct
3 Correct 67 ms 6336 KB Output is correct
4 Correct 48 ms 5048 KB Output is correct
5 Correct 54 ms 5348 KB Output is correct
6 Correct 51 ms 5308 KB Output is correct
7 Correct 52 ms 5176 KB Output is correct
8 Correct 54 ms 5352 KB Output is correct
9 Correct 51 ms 5356 KB Output is correct
10 Correct 30 ms 5184 KB Output is correct
11 Correct 30 ms 5048 KB Output is correct
12 Correct 42 ms 4980 KB Output is correct
13 Correct 42 ms 5032 KB Output is correct
14 Correct 43 ms 5048 KB Output is correct
15 Correct 55 ms 5048 KB Output is correct
16 Correct 55 ms 5048 KB Output is correct
17 Correct 48 ms 5052 KB Output is correct
18 Correct 50 ms 5176 KB Output is correct
19 Correct 48 ms 5084 KB Output is correct
20 Correct 33 ms 5552 KB Output is correct
21 Correct 33 ms 5440 KB Output is correct
22 Correct 65 ms 5352 KB Output is correct
23 Correct 47 ms 5356 KB Output is correct
24 Correct 47 ms 5440 KB Output is correct
25 Correct 46 ms 5312 KB Output is correct
26 Correct 46 ms 5304 KB Output is correct
27 Correct 47 ms 5312 KB Output is correct
28 Correct 45 ms 5320 KB Output is correct
29 Correct 42 ms 5260 KB Output is correct
30 Correct 43 ms 5244 KB Output is correct
31 Correct 5 ms 1520 KB Output is correct
32 Correct 5 ms 1656 KB Output is correct
33 Correct 5 ms 1532 KB Output is correct
34 Correct 5 ms 1668 KB Output is correct
35 Correct 4 ms 1532 KB Output is correct
36 Correct 15 ms 1520 KB Output is correct
37 Correct 5 ms 1656 KB Output is correct
38 Correct 4 ms 1532 KB Output is correct
39 Correct 4 ms 1392 KB Output is correct
40 Correct 6 ms 1628 KB Output is correct
41 Correct 5 ms 1624 KB Output is correct
42 Correct 5 ms 1520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1656 KB Output is correct
2 Correct 5 ms 1520 KB Output is correct
3 Correct 4 ms 1660 KB Output is correct
4 Correct 8 ms 2328 KB Output is correct
5 Correct 8 ms 2192 KB Output is correct
6 Correct 8 ms 2208 KB Output is correct
7 Correct 8 ms 2292 KB Output is correct
8 Correct 7 ms 2320 KB Output is correct
9 Correct 39 ms 5884 KB Output is correct
10 Correct 38 ms 5816 KB Output is correct
11 Correct 38 ms 5696 KB Output is correct
12 Correct 4 ms 1656 KB Output is correct
13 Correct 4 ms 1656 KB Output is correct
14 Correct 4 ms 1656 KB Output is correct
15 Correct 4 ms 1392 KB Output is correct

Subtask #4
38.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6172 KB Output is correct
2 Correct 69 ms 6340 KB Output is correct
3 Correct 67 ms 6436 KB Output is correct
4 Partially correct 47 ms 5184 KB Partially correct
5 Partially correct 53 ms 5568 KB Partially correct
6 Partially correct 52 ms 5328 KB Partially correct
7 Partially correct 51 ms 5176 KB Partially correct
8 Partially correct 55 ms 5244 KB Partially correct
9 Partially correct 51 ms 5344 KB Partially correct
10 Correct 31 ms 5312 KB Output is correct
11 Correct 31 ms 5408 KB Output is correct
12 Partially correct 41 ms 4904 KB Partially correct
13 Partially correct 42 ms 5108 KB Partially correct
14 Partially correct 43 ms 5044 KB Partially correct
15 Correct 55 ms 5308 KB Output is correct
16 Correct 54 ms 5056 KB Output is correct
17 Partially correct 51 ms 5068 KB Partially correct
18 Correct 50 ms 5308 KB Output is correct
19 Partially correct 51 ms 5116 KB Partially correct
20 Partially correct 33 ms 5568 KB Partially correct
21 Partially correct 33 ms 5440 KB Partially correct
22 Partially correct 45 ms 5340 KB Partially correct
23 Partially correct 47 ms 5304 KB Partially correct
24 Partially correct 46 ms 5432 KB Partially correct
25 Partially correct 46 ms 5304 KB Partially correct
26 Partially correct 45 ms 5352 KB Partially correct
27 Partially correct 47 ms 5344 KB Partially correct
28 Partially correct 46 ms 5240 KB Partially correct
29 Partially correct 41 ms 5392 KB Partially correct
30 Partially correct 43 ms 5364 KB Partially correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 6212 KB Output is correct
2 Correct 66 ms 6344 KB Output is correct
3 Correct 66 ms 6300 KB Output is correct
4 Incorrect 47 ms 5080 KB Output isn't correct
5 Halted 0 ms 0 KB -