oj.uz

Submission #63490

# Submission time Handle Problem Language Result Execution time Memory
63490 2018-08-01T23:35:38 Z reality Amusement Park (JOI17_amusement_park) C++17
10 / 100
 123 ms 51200 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 e;

static vi g[N];

static void dfs(int node,int prev) {
    e.pb(node);
    for (auto it : g[node])
        if (it != prev) {
            dfs(it,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) {
    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(0,-1);
    for (int i = 0;i < n;++i)
		MessageBoard(e[i],(X >> (i % 60)) & 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 e;

static vi g[N];

static void dfs(int node,int prev) {
    e.pb(node);
    for (auto it : g[node])
        if (it != prev) {
            dfs(it,node);
        }
}

static int f[N];

static int was[N];

static int has[N];

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

static int n;

static int Last;

static ll mask;

void DFS(int node,int prev) {
	mask ^= 1ll << was[node];
	if (Last != node) {
		int nxt = Move(node);
		if (has[node] == -1)
			has[node] = nxt;
		Last = node;
	}
	for (auto it : g[node]) {
		if (it == prev || !(mask & (1ll << was[it])))
			continue;
		DFS(it,node);
		if (Last != node)
			Move(node),Last = node;
	}
}


long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  	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(0,-1);
  	int pos = -1;
  	for (int i = 0;i < n;++i)
  		if (e[i] == P)
  			pos = i;
  	int lf = max(0,pos - 59);
  	int rg = lf + 60;
  	assert(0 <= lf && lf < rg && rg <= n);
  	assert(rg - lf == 60);
  	assert(lf <= pos && pos < rg);
  	for (int i = 0;i < n;++i)
  		was[e[i]] = (i % 60),has[i] = -1;
  	has[P] = V;
  	Last = P;
  	mask = (1ll << 60) - 1;
  	DFS(P,-1);
  	ll answer = 0;
  	for (int i = 0;i < n;++i)
  		if (has[i] != -1)
	  		answer += (1ll << was[i]) * has[i];
  	return answer;
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from Ioi.cpp:2:
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:84:25: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
    assert(0 <= lf && lf < rg && rg <= n);
                      ~~~^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47840 KB Output is correct
2 Correct 44 ms 48080 KB Output is correct
3 Incorrect 45 ms 48096 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 50396 KB Output is correct
2 Incorrect 80 ms 50516 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 50544 KB Output is correct
2 Correct 49 ms 50544 KB Output is correct
3 Correct 50 ms 50544 KB Output is correct
4 Correct 53 ms 50544 KB Output is correct
5 Correct 49 ms 50544 KB Output is correct
6 Correct 48 ms 50544 KB Output is correct
7 Correct 57 ms 50544 KB Output is correct
8 Correct 55 ms 50544 KB Output is correct
9 Correct 63 ms 51008 KB Output is correct
10 Correct 59 ms 51200 KB Output is correct
11 Correct 75 ms 51200 KB Output is correct
12 Correct 52 ms 51200 KB Output is correct
13 Correct 56 ms 51200 KB Output is correct
14 Correct 53 ms 51200 KB Output is correct
15 Correct 36 ms 51200 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 51200 KB Output is correct
2 Correct 71 ms 51200 KB Output is correct
3 Correct 73 ms 51200 KB Output is correct
4 Correct 62 ms 51200 KB Output is correct
5 Correct 72 ms 51200 KB Output is correct
6 Correct 63 ms 51200 KB Output is correct
7 Incorrect 64 ms 51200 KB Wrong Answer [7]
8 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 51200 KB Output is correct
2 Correct 71 ms 51200 KB Output is correct
3 Correct 78 ms 51200 KB Output is correct
4 Correct 78 ms 51200 KB Output is correct
5 Correct 73 ms 51200 KB Output is correct
6 Correct 72 ms 51200 KB Output is correct
7 Correct 67 ms 51200 KB Output is correct
8 Correct 74 ms 51200 KB Output is correct
9 Correct 123 ms 51200 KB Output is correct
10 Correct 65 ms 51200 KB Output is correct
11 Correct 64 ms 51200 KB Output is correct
12 Correct 69 ms 51200 KB Output is correct
13 Incorrect 62 ms 51200 KB Wrong Answer [7]
14 Halted 0 ms 0 KB -