oj.uz

Submission #41821

# Submission time Handle Problem Language Result Execution time Memory
41821 2018-02-21T09:35:09 Z cmaster Amusement Park (JOI17_amusement_park) C++14
10 / 100
 3000 ms 23912 KB 
#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
static const int MAXN2 = (int)2e5+228;
static int val2[MAXN2], used2[MAXN2];
static vector < int > g2[MAXN2];
static long long tmp, XX;
static int lvl[MAXN2];
static int mx2, timer2;
void dfs2(int v) {
	used2[v] = timer2;
	lvl[v] %= 60;
	mx2 = max(mx2, lvl[v]);
	val2[v] = (bool)((1ll << lvl[v]*1ll) & XX);
	for(auto &to : g2[v]) {
		if(used2[to] != timer2) {
			lvl[to] = lvl[v] + 1;
			dfs2(to);
		}
	}
}

void Joi(int n, int m, int A[], int B[], long long X, int T) {
  for(int i = 0; i < n; i++){
    val2[i] = -1; used2[i] = 0;
    g2[i].clear();
  }
  for(int i = 0; i < m; ++i) {
		g2[A[i]].push_back(B[i]);
		g2[B[i]].push_back(A[i]);
  }
  XX = X;
  for(int root = 0; root < n; ++root) {
  	for(int i = 0; i < n; ++i) lvl[i] = 0;
  	timer2++;
  	mx2 = 0;
		dfs2(root);
		if(mx2 == 59) break;
		assert(mx2 < 60);
	}
	assert(mx2 == 59);
	for(int i = 0; i < n; ++i) MessageBoard(i, val2[i]);
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAXN1 = (int)2e5+228;
static bool used1[MAXN1];
static vector < int > g1[MAXN1];
static int val1[MAXN1], lvl1[MAXN1], par[MAXN1], come[MAXN1];
static long long ret = 0ll;
static int mx1, timer1;
void dfs1(int v) {
	used1[v] = timer1;
	lvl1[v] %= 60;
	mx1 = max(mx1, lvl1[v]);
	for(auto &to : g1[v]) {
		if(used1[to] != timer1) {
			lvl1[to] = lvl1[v]+1;
			come[to] = v;
			dfs1(to);
		}
	}
}
static int D[MAXN1];
queue < int > qq;
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
	for(int i = 0; i < n; ++i) {
		used1[i] = 0;
		val1[i] = -1;
		g1[i].clear();
	}
	val1[P] = V;
	for(int i = 0; i < m; ++i) {
		g1[A[i]].push_back(B[i]);
		g1[B[i]].push_back(A[i]);
	}
	ret = 0ll;
	int root = 0;
	while(root < n) {
		for(int i = 0; i < n; ++i) lvl1[i] = 0;
		timer1++;
		mx1 = 0;
		dfs1(root);
		if(mx1 == 59) break;
		root++;
	}
	// return 0;
	for(int i = 0; i < n; ++i) {
		D[i] = -1;
		par[i] = -1;
		if(lvl1[i] == 59) {
			qq.push(i);
			D[i] = 0;
		}
	}
	while(!qq.empty()) {
		int v = qq.front(); qq.pop();
		for(auto &to : g1[v]) {
			if(D[to] == -1) {
				qq.push(to);
				D[to] = D[v]+1;
				par[to] = v;
			}
		}
	}
	while(lvl1[P] != 59) {
		val1[par[P]] = Move(par[P]);
		P = par[P];
	}
	assert(lvl1[P] == 59);
	while(lvl1[P] > 0) {
		ret |= (1ll << lvl1[P]) * val1[P];
		val1[come[P]] = Move(come[P]);
		P = come[P];
	}
	assert(lvl1[P] == 0);
	ret |= (1ll << lvl1[P]) * val1[P];
  return ret;
}

Compilation message

Joi.cpp:7:18: warning: 'tmp' defined but not used [-Wunused-variable]
 static long long tmp, XX;
                  ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 23120 KB Output is correct
2 Correct 41 ms 23360 KB Output is correct
3 Correct 40 ms 23424 KB Output is correct
4 Execution timed out 3038 ms 11712 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23424 KB Output is correct
2 Correct 11 ms 23424 KB Output is correct
3 Correct 11 ms 23424 KB Output is correct
4 Correct 12 ms 23424 KB Output is correct
5 Correct 13 ms 23424 KB Output is correct
6 Correct 16 ms 23424 KB Output is correct
7 Correct 15 ms 23424 KB Output is correct
8 Correct 13 ms 23424 KB Output is correct
9 Correct 25 ms 23424 KB Output is correct
10 Correct 23 ms 23424 KB Output is correct
11 Correct 23 ms 23424 KB Output is correct
12 Correct 10 ms 23424 KB Output is correct
13 Correct 11 ms 23424 KB Output is correct
14 Correct 10 ms 23424 KB Output is correct
15 Correct 12 ms 23424 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 23668 KB Output is correct
2 Correct 39 ms 23912 KB Output is correct
3 Correct 44 ms 23912 KB Output is correct
4 Execution timed out 3101 ms 11956 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 23912 KB Output is correct
2 Correct 41 ms 23912 KB Output is correct
3 Correct 43 ms 23912 KB Output is correct
4 Execution timed out 3084 ms 11956 KB Time limit exceeded
5 Halted 0 ms 0 KB -