oj.uz

Submission #676870

# Submission time Handle Problem Language Result Execution time Memory
676870 2023-01-01T12:33:17 Z radal Amusement Park (JOI17_amusement_park) C++17
0 / 100
 3000 ms 50524 KB 
#include <bits/stdc++.h>
#include "Joi.h"
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 1e6+10,mod = 1e9+7;

vector<int> adj[N];
int T,tin[N];
bool vis[N];

void dfs(int v,ll x){
	if ((x&(1ll << (T%60)))) MessageBoard(v,1);
	else MessageBoard(v,0);
	tin[v] = T++;
	vis[v] = 1;
	for (int u : adj[v]) if (!vis[u]) dfs(u,x);
}

void Joi(int n, int m, int A[], int B[], long long x, int tt) {
	rep(i,0,m){
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	rep(i,0,n) sort(all(adj[i]));
	dfs(0,x);
	return;
}

#include "Ioi.h"
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;

using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 1e6+10,mod = 1e9+7;
constexpr ll inf = 1e9+10;

vector<int> adj[N];
bool vis[N];
int tin[N],T;
int par[N],ans[70];
int po[N];

void dfs(int v){
	vis[v] = 1;
	tin[v] = T++;
	for (int u : adj[v]) if (!vis[u]){
		par[v] = u;
	   	dfs(u);
	}
}

long long Ioi(int n, int m, int A[], int B[], int P, int v, int tt) {
	rep(i,0,m){
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	rep(i,0,n) sort(all(adj[i]));
	dfs(0);
	memset(ans,-1,sizeof ans);
	int cur = v;
	ans[tin[cur]%60] = P;
	int cnt = 1;
	while (cnt < 60){
		int fl = -1;
		int sz = adj[cur].size();
		while (po[cur] < sz){
			int u = adj[cur][po[cur]];
			if (u == par[cur]) continue;
			po[cur]++;
			if (ans[tin[u]%60] == -1) continue;
			fl = u;		
		}
		if (fl == -1)
			fl = par[cur];
		int t = tin[fl]%60;
		if (ans[t] == -1) cnt++;
		ans[t] = move(fl);
		cur = fl;
	}
	ll out = 0;
	rep(i,0,60) if (ans[i]) out += (1ll << i);
	return out;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3084 ms 47628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 50524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 47648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 50476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 50488 KB Time limit exceeded
2 Halted 0 ms 0 KB -