oj.uz

Submission #63488

# Submission time Handle Problem Language Result Execution time Memory
63488 2018-08-01T23:31:32 Z reality Amusement Park (JOI17_amusement_park) C++17
10 / 100
 121 ms 100148 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;

void DFS(int node,int prev) {
	if (Last != node) {
		int nxt = Move(node);
		if (has[node] == -1)
			has[node] = nxt;
		Last = node;
	}
	for (auto it : g[node]) {
		if (it == prev || was[it] == -1)
			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[i] = -1,has[i] = -1;
  	for (int i = lf;i < rg;++i)
  		was[e[i]] = (i % 60);
  	has[P] = V;
  	Last = P;
  	DFS(P,-1);
  	ll answer = 0;
  	for (int i = 0;i < n;++i)
  		if (was[i] != -1)
	  		assert(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:81: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 50 ms 47736 KB Output is correct
2 Runtime error 82 ms 71684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 120 ms 98680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 99776 KB Output is correct
2 Correct 53 ms 99776 KB Output is correct
3 Correct 53 ms 99776 KB Output is correct
4 Correct 49 ms 99776 KB Output is correct
5 Correct 56 ms 99776 KB Output is correct
6 Correct 47 ms 99776 KB Output is correct
7 Correct 50 ms 99776 KB Output is correct
8 Correct 47 ms 99776 KB Output is correct
9 Correct 56 ms 99968 KB Output is correct
10 Correct 68 ms 100032 KB Output is correct
11 Correct 71 ms 100032 KB Output is correct
12 Correct 47 ms 100032 KB Output is correct
13 Correct 49 ms 100032 KB Output is correct
14 Correct 44 ms 100032 KB Output is correct
15 Correct 49 ms 100032 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 107 ms 100064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 121 ms 100148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -