Submission #1202651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202651		LIA	Amusement Park (JOI17_amusement_park)	C++20	0 / 100	16 ms	2116 KiB

Joi

// Joi.cpp
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;

static vvll g;
static vb vis;
static ll cnt;
static void dfs(ll node) {
  if (cnt == 0) return;
  cnt--;
  MessageBoard(node, 1);
  vis[node] = true;
  for (auto it : g[node]) {
	if (!vis[it]) dfs(it);
  }
}

void Joi(int n, int m, int a[], int b[], long long x, int t) {
  cnt = x;
  g.assign(n, {});
  vis.assign(n, false);

  for (int i = 0; i < m; i++) {
	int ai = a[i], bi = b[i];
	g[ai].push_back(bi);
	g[bi].push_back(ai);
  }
  for (int u = 0; u < n; u++) {
	sort(g[u].begin(), g[u].end());
  }
  dfs(0);
  for (int i = 0; i < n; i++) {
	if (!vis[i]) MessageBoard(i, 0);
  }
}

Ioi

// Ioi.cpp
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;

static vvll ad;
static vb vis1;
static ll cnt1;

static void dfs(int node) {
  vis1[node] = true;
  for (int nxt : ad[node]) {
	if (!vis1[nxt]) {
	  ll a = Move(nxt);   // go down one edge
	  cnt1+=a;
	  dfs(nxt);
	  ll b = Move(node);  // come right back up one edge
	}
  }
}
long long Ioi(int n, int m, int a[], int b[], int p, int v, int t) {
  // 1) בנה גרף ממויין
  vector<vector<int>> ad(n);
  for(int i=0;i<m;i++){
	ad[a[i]].push_back(b[i]);
	ad[b[i]].push_back(a[i]);
  }
  for(int u=0;u<n;u++) sort(ad[u].begin(), ad[u].end());

  // 2) חשב parent[] ע"י BFS מ־0
  vector<int> parent(n, -1);
  queue<int> q;
  parent[0] = 0;
  q.push(0);
  while(!q.empty()){
	int u = q.front(); q.pop();
	for(int w: ad[u]){
	  if(parent[w] == -1){
		parent[w] = u;
		q.push(w);
	  }
	}
  }

  // 3) העבר מ-p ל-0
  int cur = p;
  while(cur != 0){
	int par = parent[cur];
	Move(par);
	cur = par;
  }

  // 4) אתחל ותחל במסע ה-DFS
  cnt1 = v;
  vis1.assign(n,false);
  dfs(0);

  return cnt1;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17