oj.uz

답안 #566197

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
566197 2022-05-22T05:33:16 Z 8e7 Flights (JOI22_flights) C++17
63 / 100
 302 ms 2880 KB 
//Challenge: Accepted
#include "Ali.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 10005
#define pii pair<int, int>
#define ff first
#define ss second
	const int bs = 10;
	vector<int> adj[maxn];
	int bid[maxn], bord[maxn], siz[maxn], par[maxn], dep[maxn], id[maxn];	
	bool isroot[maxn];
	int root[maxn];
	string trav[maxn];
	int C = 0;
	
	int st;
	void dfs(int n, int pa, int d) {
		par[n] = pa;
		dep[n] = d;
		siz[n] = 1;
		debug(n);
		for (int v:adj[n]) {
			if (v != pa) {
				dfs(v, n, d+1);
				if (siz[v] < bs) {
					siz[n] += siz[v];
				}
			}
		}
		if (siz[n] >= bs || n == st) {
			debug("root", n, siz[n]);
			isroot[n] = 1;
			bid[n] = C;
			root[C++] = n;
		}
	}
	void getb(int n, int pa, int &ti) {
		bord[n] = ti++;
		
		for (int v:adj[n]) {
			if (v != pa && !isroot[v]) {
				trav[bid[n]] += '1';
				bid[v] = bid[n];
				getb(v, n, ti);
				trav[bid[n]] += '0';
			}
		}
	}
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
	for (int i = 0;i < N;i++) {
		adj[i].clear();
		trav[i].clear();
		bid[i] = 0, bord[i] = 0;
		siz[i] = 0;
		isroot[i] = 0, root[i] = 0;
	}
	C = 0;

	for (int i = 0;i < N - 1;i++) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	for (int i = 0;i < N;i++) {
		if (adj[i].size() == 1) {
			st = i;
			dfs(st, -1, 0);
			break;
		}
	}
	
	for (int i = 0;i < N;i++) {
		if (isroot[i]) {
			int tmp = 0;
			getb(i, par[i], tmp);
		}
	}
	for (int i = 0;i < C;i++) {
		while (trav[i].size() < 36) trav[i] += '0';
	}
	for (int i = 0;i < N;i++) {
		id[i] = bid[i] * 2 * bs + bord[i];	
		//debug(bid[i], bord[i]);
		SetID(i, id[i]);
	}
}

std::string SendA(std::string S) {
	int bx = 0, by = 0;
	for (int i = 0;i < 10;i++) bx += (S[i] - '0') * (1<<i);
	for (int i = 10;i < 20;i++) by += (S[i] - '0') * (1<<(i-10));
	debug("senda", bx, by);

	int dis = 0;	
	int px = root[bx], py = root[by], v = 0;
	while (px != py) {
		if (dep[px] < dep[py]) swap(px, py);
		px = par[px];
		dis++;
		if (bid[px] == bid[py] && bid[px] == bx) {
			v = bord[px];	
			break;
		}
	}
	debug(dis);

	string ret;
	for (int i = 0;i < 14;i++) ret += char(((dis >> i) & 1) + '0'); 
	ret.insert(ret.end(), trav[bx].begin(), trav[bx].end());
	ret.insert(ret.end(), trav[by].begin(), trav[by].end());
	for (int i = 0;i < 5;i++) ret += char(((v >> i) & 1) + '0');	
	debug(ret);
	return ret;
}

//Challenge: Accepted
#include "Benjamin.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define maxn 10005
#define pii pair<int, int>
#define ff first
#define ss second
namespace {
#ifdef zisk
	void debug(){cout << endl;}
	template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
	template<class T> void pary(T l, T r) {
		while (l != r) cout << *l << " ", l++;
		cout << endl;
	}
#else
#define debug(...) 0
#define pary(...) 0
#endif
	const int bs = 10;
	int bx, by, dx, dy;
	int par[maxn], dep[maxn];
	void decode(string s) {
		int d = 0, cur = 0, id = 0;
		dep[cur] = 0;
		for (auto i:s) {
			d += (i == '1' ? 1 : -1);
			if (i - '0') {
				dep[++id] = d;
				par[id] = cur;
				cur = id;
			} else {
				if (d < 0) return;
				cur = par[cur];
			}
		}
	}
}

std::string SendB(int N, int X, int Y) {
	bx = X / (2 * bs), by = Y / (2 * bs);	
	dx = X % (2 * bs), dy = Y % (2 * bs);
	if (bx < by) swap(bx, by), swap(dx, dy);
	string ret;
	for (int i = 0;i < 10;i++) ret += char(((bx >> i) & 1) + '0');
	for (int i = 0;i < 10;i++) ret += char(((by >> i) & 1) + '0');
	debug(bx, dx, by, dy);
	return ret;
}

int Answer(std::string T) {
	int ret = 0;
	for (int i = 0;i < 14;i++) {
		ret += (1<<i) * (T[i] - '0');
	}
	if (bx != by) {
		decode(T.substr(14, 36));	
		int v = 0;	
		for (int i = 0;i < 5;i++) v += (1<<i) * (T[86 + i] - '0');
		if (v) {
			while (dx != v) {
				if (dep[dx] < dep[v]) swap(dx, v);
				dx = par[dx];
				ret++;
			}
		} else {
			ret += dep[dx];
		}

		decode(T.substr(50, 36));
		ret += dep[dy];	
	} else {
		decode(T.substr(14, 36));
		while (dx != dy) {
			if (dep[dx] < dep[dy]) swap(dx, dy);
			dx = par[dx];
			ret++;
		}
	}
	return ret;
}

Compilation message

Ali.cpp: In function 'void {anonymous}::dfs(int, int, int)':
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Ali.cpp:36:3: note: in expansion of macro 'debug'
   36 |   debug(n);
      |   ^~~~~
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Ali.cpp:46:4: note: in expansion of macro 'debug'
   46 |    debug("root", n, siz[n]);
      |    ^~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Ali.cpp:108:2: note: in expansion of macro 'debug'
  108 |  debug("senda", bx, by);
      |  ^~~~~
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Ali.cpp:121:2: note: in expansion of macro 'debug'
  121 |  debug(dis);
      |  ^~~~~
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Ali.cpp:128:2: note: in expansion of macro 'debug'
  128 |  debug(ret);
      |  ^~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'std::string SendB(int, int, int)':
Benjamin.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 0
      |                    ^
Benjamin.cpp:50:2: note: in expansion of macro 'debug'
   50 |  debug(bx, dx, by, dy);
      |  ^~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1040 KB Output is correct
3 Correct 2 ms 1136 KB Output is correct
4 Correct 1 ms 1040 KB Output is correct
5 Correct 1 ms 1132 KB Output is correct
6 Correct 8 ms 1952 KB Output is correct
7 Correct 9 ms 1900 KB Output is correct
8 Correct 9 ms 1908 KB Output is correct
9 Correct 9 ms 1904 KB Output is correct
10 Correct 7 ms 2072 KB Output is correct
11 Correct 6 ms 1680 KB Output is correct
12 Correct 9 ms 1900 KB Output is correct
13 Correct 7 ms 1904 KB Output is correct
14 Correct 5 ms 2028 KB Output is correct
15 Correct 7 ms 2700 KB Output is correct
16 Correct 7 ms 2024 KB Output is correct

Subtask #2
48.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 1040 KB Output is partially correct
2 Partially correct 50 ms 2632 KB Output is partially correct
3 Partially correct 3 ms 1040 KB Output is partially correct
4 Partially correct 302 ms 2008 KB Output is partially correct
5 Partially correct 223 ms 2028 KB Output is partially correct
6 Partially correct 247 ms 2032 KB Output is partially correct
7 Partially correct 239 ms 2808 KB Output is partially correct
8 Partially correct 224 ms 2012 KB Output is partially correct
9 Partially correct 223 ms 2496 KB Output is partially correct
10 Partially correct 211 ms 2864 KB Output is partially correct
11 Partially correct 208 ms 1892 KB Output is partially correct
12 Partially correct 25 ms 1832 KB Output is partially correct
13 Partially correct 129 ms 1960 KB Output is partially correct
14 Partially correct 146 ms 1924 KB Output is partially correct
15 Partially correct 6 ms 1128 KB Output is partially correct
16 Partially correct 209 ms 2808 KB Output is partially correct
17 Partially correct 241 ms 2880 KB Output is partially correct
18 Partially correct 215 ms 2484 KB Output is partially correct
19 Partially correct 198 ms 2584 KB Output is partially correct
20 Partially correct 133 ms 2324 KB Output is partially correct
21 Partially correct 184 ms 2552 KB Output is partially correct
22 Partially correct 212 ms 2028 KB Output is partially correct
23 Partially correct 190 ms 1932 KB Output is partially correct
24 Partially correct 188 ms 2020 KB Output is partially correct
25 Partially correct 196 ms 2080 KB Output is partially correct
26 Partially correct 201 ms 2016 KB Output is partially correct
27 Partially correct 196 ms 2024 KB Output is partially correct
28 Partially correct 220 ms 2008 KB Output is partially correct
29 Partially correct 195 ms 1924 KB Output is partially correct
30 Partially correct 219 ms 2060 KB Output is partially correct
31 Partially correct 201 ms 2128 KB Output is partially correct
32 Partially correct 243 ms 1992 KB Output is partially correct
33 Partially correct 259 ms 1960 KB Output is partially correct
34 Partially correct 199 ms 1928 KB Output is partially correct
35 Partially correct 215 ms 1940 KB Output is partially correct
36 Partially correct 202 ms 2092 KB Output is partially correct
37 Partially correct 192 ms 1936 KB Output is partially correct
38 Partially correct 208 ms 2012 KB Output is partially correct
39 Partially correct 33 ms 2020 KB Output is partially correct
40 Partially correct 236 ms 2680 KB Output is partially correct