2022 Niuke multi school second problem solving Report

A.Ancestor

Ideas : Multiple points in the tree lca by dfs The sum of the smallest order dfs The two points with the largest order lca, Enumerate and then find lca that will do

skill :

Code :

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define eps 1e-8
int T = 1;
using namespace std;
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c-o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x);*x = 0; return *this;} template<typename t> q&operator>>(t&x){for (r(y),s=0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p!=h) w(*--p);return *this;}}qio; }using nqio::qio;
const int N = 1e6 + 10;

int n, k, x[N], a[N], b[N];
struct KK {
	int h[N], v[N], to[N], tot;
	int tpf[N], fa[N], sz[N], son[N], dep[N], in[N], tim;
	void add(int a, int b) {v[++tot] = b, to[tot] = h[a], h[a] = tot;}
	void dfs1(int x, int f, int depth) {
		dep[x] = depth; fa[x] = f, sz[x] = 1;
		int mxsz = -1;
		for (int i = h[x]; i; i = to[i]) {
			int y = v[i];
			if (y == f) continue;
			dfs1(y, x, depth + 1);
			sz[x] += sz[y];
			if (mxsz < sz[y]) mxsz = sz[y], son[x] = y;
		}
	}
	void dfs2(int x, int topf) {
		in[x] = ++tim, tpf[x] = topf;
		if (!son[x]) return;
		dfs2(son[x], topf);
		for (int i = h[x]; i; i = to[i]) {
			int y = v[i];
			if (y == fa[x] || y == son[x]) continue;
			dfs2(y, y);
		}
	}
	void init() {
		for (int i = 1; i <= n; ++i) h[i] = 0;
		tim = tot = 0;
	}
	void work() {
		dfs1(1, -1, 1); dfs2(1, 1);
	}
	int LCA(int x, int y) {
		while (tpf[x] != tpf[y]) {
			if (dep[tpf[x]] < dep[tpf[y]]) swap(x, y);
			x = fa[tpf[x]];
		}
		if (dep[x] > dep[y]) swap(x, y);
		return x;
	}
} A, B;
struct recA {
	int x;
	bool operator< (const recA& i) const {
		return A.in[x] < A.in[i.x];
	}
};
struct recB {
	int x;
	bool operator< (const recB& i) const {
		return B.in[x] < B.in[i.x];
	}
};
void solve() {	
	qio >> n >> k;
	set<recA> sa;
	set<recB> sb;
	for (int i = 1; i <= k; ++i) qio >> x[i];
	A.init(), B.init();
	for (int i = 1; i <= n; ++i) qio >> a[i];
	for (int i = 2; i <= n; ++i) {int x; qio >> x; A.add(i, x); A.add(x, i);}
	for (int i = 1; i <= n; ++i) qio >> b[i];
 	for (int i = 2; i <= n; ++i) {int x; qio >> x; B.add(i, x); B.add(x, i);}
	A.work(), B.work();
	for (int i = 1; i <= k; ++i) sa.insert({x[i]}), sb.insert({x[i]});
	int ans = 0;
	for (int i = 1; i <= k; ++i) {
		sa.erase({x[i]}), sb.erase({x[i]});
		int la = A.LCA((*sa.begin()).x, (*sa.rbegin()).x);
		int lb = B.LCA((*sb.begin()).x, (*sb.rbegin()).x);
		if (a[la] > b[lb]) ++ans;
		sa.insert({x[i]}), sb.insert({x[i]});
	}	
	qio << ans << "\n";
}
signed main() {
	IOS;
	while (T--) solve();
}

C.Concatenation

Ideas : heavy load <,return AB < BA

Code :

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define eps 1e-8
int T = 1;
using namespace std;
namespace nqio{const unsigned R=4e5,W=4e5;char*a,*b,i[R],o[W],*c=o,*d=o+W,h[40],*p=h,y;bool s;struct q{void r(char&x){x=a==b&&(b=(a=i)+fread(i,1,R,stdin),a==b)?-1:*a++;}void f(){fwrite(o,1,c-o,stdout);c=o;}~q(){f();}void w(char x){*c=x;if(++c==d)f();}q&operator>>(char&x){do r(x);while(x<=32);return*this;}q&operator>>(char*x){do r(*x);while(*x<=32);while(*x>32)r(*++x);*x=0;return*this;}template<typename t>q&operator>>(t&x){for(r(y),s=0;!isdigit(y);r(y))s|=y==45;if(s)for(x=0;isdigit(y);r(y))x=x*10-(y^48);else for(x=0;isdigit(y);r(y))x=x*10+(y^48);return*this;}q&operator<<(char x){w(x);return*this;}q&operator<<(char*x){while(*x)w(*x++);return*this;}q&operator<<(const char*x){while(*x)w(*x++);return*this;}template<typename t>q&operator<<(t x){if(!x)w(48);else if(x<0)for(w(45);x;x/=10)*p++=48|-(x%10);else for(;x;x/=10)*p++=48|x%10;while(p!=h)w(*--p);return*this;}}qio;}using nqio::qio;
const int N = 2e6 + 10;
string s[N];
bool cmp(string &A, string &B) {return A + B < B + A;}
void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> s[i];
    sort(s + 1, s + 1 + n, cmp);
    for (int i = 1; i <= n; ++i) cout << s[i];
}
signed main() {
	IOS;
	while (T--) solve();
}

F.Fief

Ideas : The title requires finding two points on the graph , Then make it start from any of these points " burn ", Will not give the whole picture to " Burn out "( Separate the area occupied by these two points ). This reminds us to think about it . The first obvious point is , When the whole graph has only one point two-way component or only two points , There must be a solution . If the whole graph is disconnected , There must be no solution . Next , Let's consider finding dot pairs and then shrinking . You can find , When a dot pair has 3 More than sons , No matter where these two points are , Start from one of the points , It will burn this picture . therefore , The double degree of a point is less than or equal to 2, in other words , Is chain . If two points are at both ends of the chain , Obviously, this is satisfying . Otherwise, unless there is only one dot double , Neither of the two points can be in one point pair . There is also a case of , At least one of the two points is not on the chain , That's not going to work .

  Code :

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 1e6 + 10;
int n, m;
int h[N], v[N], to[N], tot;
int dfn[N], low[N], tim, cut[N], cnt, dd[N], top;
vector<int> stk;
set<int> bcc[N];
void add(int a, int b) {v[++tot] = b, to[tot] = h[a], h[a] = tot;}
void tarjan(int x) {
	dfn[x] = low[x] = ++tim;
	stk.emplace_back(x);
	int flag = 0;
	for (int i = h[x]; i; i = to[i]) {
		int y = v[i];
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x]) {
				++flag;
				if (x != 1 || flag > 1) cut[x] = true;
				++cnt;
				int p;
				do {
					p = stk.back();
					stk.pop_back();
					bcc[p].insert(cnt);
					//bcc[cnt].insert(p);
				} while (p != y);
				bcc[x].insert(cnt);
				//bcc[cnt].insert(p);
			}
		}else {
			low[x] = min(low[x], dfn[y]);
		}
	}
}
signed main() {
	qio >> n >> m;
	for (int i = 1; i <= m; ++i) {int a, b; qio >> a >> b; add(a, b), add(b, a);}
	// Find the dot double pass component 
	tarjan(1);
	bool ok = 1;
	// If the graph is not connected  pass
	for (int i = 1; i <= n; ++i) if (!dfn[i]) ok = 0;
	int q;
	qio >> q;
	// If the degree of a certain cut point is greater than or equal to 3 pass
	for (int i = 1; i <= n; ++i) if (bcc[i].size() > 2) ok = 0;
 	for (int i = 1; i <= n; ++i) {
 		if (bcc[i].size() == 2) 
 			for (int x : bcc[i]) 
 				++dd[x];
 	}
 	// If the degree of a connected component is greater than or equal to 3 pass
	for (int i = 1; i <= cnt; ++i) if (dd[i] >= 3) ok = 0;
	int A = 0, B = 0;
	// Find the two ends of the connected component chain A, B, If there is only one point , Then itself is both ends 
	for (int i = 1; i <= cnt; ++i) if (dd[i] == 1) (A ? B : A) = i;
	if (!A) A = B = 1;
	// If there are only two points  √
	if (n == 2) {
		while (q--) qio << "YES\n";
		return 0;
	}
	if (!ok) {
		while (q--) qio << "NO\n";
		return 0;
	}
	while (q--) {
		int u, v;
		qio >> u >> v;
		// If a point belongs to two connected components at the same time , Description is the cut point  pass
		if (bcc[u].size() >= 2 || bcc[v].size() >= 2) qio << "NO\n";
		else {
			int uu = *(bcc[u].begin()), vv = *(bcc[v].begin());
			// If not at both ends of the chain  pass
			if ((uu == A && vv == B) || (uu == B && vv == A)) qio << "YES\n";
			else qio << "NO\n";
		}
	}
	
}

D.Journey

Ideas : Create a drawing between the edges , The right side right is 0, Others are 1, Optimize with double ended queues bfs.

skill : Grid mapping

Code :

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f

namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 2e7 + 10;
int h[N], v[N], to[N], w[N], tot, n, f[N][5], s1, s2, t1, t2, d[N];
void add(int a, int b, int c) {w[++tot] = c, v[tot] = b, to[tot] = h[a], h[a] = tot; /*qio << a <<  " -> " << b << " is " << c << "\n";*/}
int pos(int x, int y) {return (x - 1) * 4 + y + 1;}
int find(int x, int y) {for (int i = 0; i < 4; ++i) if (f[x][i] == y) return pos(x, i); return 0;}
signed main() {
	qio >> n;
	for (int i = 1; i <= n; ++i) for (int j = 0; j < 4; ++j) qio >> f[i][j];
	for (int i = 1; i <= n; ++i) for (int j = 0; j < 4; ++j)
		if (f[i][j]) {
			add(find(f[i][j], i), pos(i, j), 1);
			if (f[i][(j + 1) % 4]) add(find(f[i][(j + 1) % 4], i), pos(i, j), 1);
			if (f[i][(j + 2) % 4]) add(find(f[i][(j + 2) % 4], i), pos(i, j), 1);
			if (f[i][(j + 3) % 4]) add(find(f[i][(j + 3) % 4], i), pos(i, j), 0);
		}
	qio >> s1 >> s2 >> t1 >> t2;
	int st = find(s1, s2), ed = find(t1, t2);
	deque<int> dq;
	mem(d, 0x3f);
	dq.push_back(st); d[st] = 0;
	while (SZ(dq)) {
		int x = dq.front(); dq.pop_front();
		for (int i = h[x], y; i; i = to[i]) {
            y = v[i];
			if (d[y] <= d[x] + w[i]) continue;
			d[y] = d[x] + w[i];
			if (!w[i]) dq.push_front(y);
			else dq.push_back(y);
		}
	}
	qio << (d[ed] > inf ? -1 : d[ed]) << "\n";
}