oj.uz

Submission #63473

# Submission time Handle Problem Language Result Execution time Memory
63473 2018-08-01T22:34:14 Z reality Amusement Park (JOI17_amusement_park) C++17
28 / 100
 110 ms 75032 KB 
#include "Joi.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1e6 + 5;

static vi Euler;

static int was[N];

static int ok[N];

static vi g[N];

static int T = -1;

static void dfs(int node,int prev) {
    T = (T + 1) % 60;
    ok[Euler.size()] = T;
    Euler.pb(node);
    for (auto it : g[node])
        if (it != prev) {
            dfs(it,node);
            Euler.pb(node);
        }
}

static int f[N];

static int get(int k) {
    return k == f[k] ? k : f[k] = get(f[k]);
}

static int n;

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    srand(696969);
    memset(ok,-1,sizeof(ok));
  	n = N;
    for (int i = 0;i < n;++i)
  		f[i] = i;
  	for (int i = 0;i < M;++i) {
  		if (get(A[i]) == get(B[i]))
  			continue;
  		g[A[i]].pb(B[i]);
  		g[B[i]].pb(A[i]);
  		f[get(A[i])] = get(B[i]);
  	}
  	dfs(rand() % n,-1);
  	int sz = Euler.size();
    for (int i = 0;i < sz;++i)
  		if (ok[i] != -1)
  			MessageBoard(Euler[i],(X >> ok[i]) & 1);
}

#include "Ioi.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1e6 + 5;

static vi Euler;

static int was[N];

static int ok[N];

static int W[N];

static vi g[N];

static int T = -1;

static void dfs(int node,int prev) {
	T = (T + 1) % 60;
    ok[Euler.size()] = T;
    W[node] = T;
    Euler.pb(node);
    for (auto it : g[node])
        if (it != prev) {
            dfs(it,node);
            Euler.pb(node);
        }
}

static int f[N];

static int get(int k) {
	return k == f[k] ? k : f[k] = get(f[k]);
}

static int n;

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  	srand(696969);
  	memset(ok,-1,sizeof(ok));
  	n = N;
  	for (int i = 0;i < n;++i)
  		f[i] = i;
  	for (int i = 0;i < M;++i) {
  		if (get(A[i]) == get(B[i]))
  			continue;
  		g[A[i]].pb(B[i]);
  		g[B[i]].pb(A[i]);
  		f[get(A[i])] = get(B[i]);
  	}
  	dfs(rand() % n,-1);
  	int sz = Euler.size();
  	ll mask = (1ll << 60) - 1;
  	int pos = -1;
  	for (int i = 0;i < sz;++i)
  		if (Euler[i] == P) {
  			pos = i;
  			break;
  		}
  	ll answer = 0;
  	answer |= V * (1ll << W[Euler[pos]]);
  	mask ^= (1ll << W[Euler[pos]]);
  	for (int i = (pos + 1) % sz,j = pos;mask;i = (i + 1) % sz,j = (j + 1) % sz)  {
  		if (Euler[i] == Euler[j])
  			continue;
  		int nxt = Move(Euler[i]);
  		if (mask & (1ll << W[Euler[i]])) {
  			mask ^= 1ll << W[Euler[i]];
  			answer |= nxt * (1ll << W[Euler[i]]); 
  		}
  	}
  	return answer;
}

Compilation message

Joi.cpp:22:12: warning: 'was' defined but not used [-Wunused-variable]
 static int was[N];
            ^~~

Ioi.cpp:22:12: warning: 'was' defined but not used [-Wunused-variable]
 static int was[N];
            ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 55660 KB Output is correct
2 Correct 57 ms 55992 KB Output is correct
3 Correct 62 ms 56168 KB Output is correct
4 Correct 55 ms 56396 KB Output is correct
5 Correct 49 ms 56480 KB Output is correct
6 Correct 67 ms 56480 KB Output is correct
7 Correct 66 ms 56480 KB Output is correct
8 Correct 52 ms 56480 KB Output is correct
9 Correct 53 ms 56480 KB Output is correct
10 Correct 49 ms 56480 KB Output is correct
11 Correct 55 ms 56952 KB Output is correct
12 Correct 54 ms 56952 KB Output is correct
13 Correct 60 ms 56952 KB Output is correct
14 Correct 60 ms 56952 KB Output is correct
15 Correct 61 ms 56952 KB Output is correct
16 Correct 52 ms 56952 KB Output is correct
17 Correct 68 ms 56952 KB Output is correct
18 Correct 57 ms 56952 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 59436 KB Output is correct
2 Correct 89 ms 59820 KB Output is correct
3 Correct 96 ms 60204 KB Output is correct
4 Correct 80 ms 60208 KB Output is correct
5 Correct 79 ms 60472 KB Output is correct
6 Correct 72 ms 60652 KB Output is correct
7 Correct 82 ms 60792 KB Output is correct
8 Correct 82 ms 60896 KB Output is correct
9 Correct 84 ms 61096 KB Output is correct
10 Correct 76 ms 61096 KB Output is correct
11 Correct 81 ms 61244 KB Output is correct
12 Correct 84 ms 61320 KB Output is correct
13 Correct 74 ms 61544 KB Output is correct
14 Correct 83 ms 61976 KB Output is correct
15 Correct 81 ms 62088 KB Output is correct
16 Correct 74 ms 62312 KB Output is correct
17 Correct 96 ms 62416 KB Output is correct
18 Correct 86 ms 62568 KB Output is correct
19 Correct 79 ms 62696 KB Output is correct
20 Correct 67 ms 63292 KB Output is correct
21 Correct 63 ms 63544 KB Output is correct
22 Correct 72 ms 63684 KB Output is correct
23 Correct 77 ms 63784 KB Output is correct
24 Correct 68 ms 64112 KB Output is correct
25 Correct 78 ms 64392 KB Output is correct
26 Correct 76 ms 64512 KB Output is correct
27 Correct 73 ms 64624 KB Output is correct
28 Correct 78 ms 64728 KB Output is correct
29 Correct 71 ms 64908 KB Output is correct
30 Correct 79 ms 65268 KB Output is correct
31 Correct 52 ms 65352 KB Output is correct
32 Correct 52 ms 65352 KB Output is correct
33 Correct 51 ms 65352 KB Output is correct
34 Correct 58 ms 65352 KB Output is correct
35 Correct 57 ms 65352 KB Output is correct
36 Correct 62 ms 65352 KB Output is correct
37 Correct 51 ms 65352 KB Output is correct
38 Correct 54 ms 65352 KB Output is correct
39 Correct 60 ms 65352 KB Output is correct
40 Correct 49 ms 65352 KB Output is correct
41 Correct 60 ms 65352 KB Output is correct
42 Correct 57 ms 65352 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 65352 KB Output is correct
2 Correct 54 ms 65352 KB Output is correct
3 Correct 63 ms 65352 KB Output is correct
4 Correct 62 ms 65352 KB Output is correct
5 Correct 64 ms 65352 KB Output is correct
6 Correct 51 ms 65352 KB Output is correct
7 Correct 59 ms 65352 KB Output is correct
8 Correct 59 ms 65352 KB Output is correct
9 Correct 70 ms 65856 KB Output is correct
10 Correct 72 ms 66392 KB Output is correct
11 Correct 84 ms 66560 KB Output is correct
12 Correct 61 ms 66608 KB Output is correct
13 Correct 55 ms 66608 KB Output is correct
14 Correct 56 ms 66608 KB Output is correct
15 Correct 51 ms 66608 KB Output is correct

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 66692 KB Output is correct
2 Correct 88 ms 67044 KB Output is correct
3 Correct 88 ms 67384 KB Output is correct
4 Correct 79 ms 67464 KB Output is correct
5 Partially correct 80 ms 67944 KB Partially correct
6 Correct 79 ms 68112 KB Output is correct
7 Correct 90 ms 68112 KB Output is correct
8 Correct 73 ms 68312 KB Output is correct
9 Correct 68 ms 68332 KB Output is correct
10 Correct 73 ms 68420 KB Output is correct
11 Correct 77 ms 68492 KB Output is correct
12 Correct 77 ms 68568 KB Output is correct
13 Correct 110 ms 68680 KB Output is correct
14 Correct 78 ms 68996 KB Output is correct
15 Correct 77 ms 69188 KB Output is correct
16 Correct 84 ms 69336 KB Output is correct
17 Correct 80 ms 69744 KB Output is correct
18 Correct 77 ms 69944 KB Output is correct
19 Correct 82 ms 70236 KB Output is correct
20 Incorrect 73 ms 70776 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 71240 KB Output is correct
2 Correct 86 ms 71816 KB Output is correct
3 Correct 90 ms 72040 KB Output is correct
4 Correct 80 ms 72128 KB Output is correct
5 Correct 77 ms 72248 KB Output is correct
6 Correct 92 ms 72336 KB Output is correct
7 Correct 70 ms 72504 KB Output is correct
8 Correct 67 ms 72632 KB Output is correct
9 Correct 80 ms 72860 KB Output is correct
10 Correct 83 ms 72948 KB Output is correct
11 Correct 76 ms 72972 KB Output is correct
12 Correct 72 ms 73072 KB Output is correct
13 Correct 75 ms 73232 KB Output is correct
14 Correct 76 ms 73480 KB Output is correct
15 Correct 92 ms 73656 KB Output is correct
16 Correct 82 ms 73876 KB Output is correct
17 Correct 84 ms 74040 KB Output is correct
18 Correct 93 ms 74232 KB Output is correct
19 Correct 86 ms 74456 KB Output is correct
20 Incorrect 76 ms 75032 KB Output isn't correct
21 Halted 0 ms 0 KB -