Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 2600 teams from all over the world registering for Universal Cup.

A more detailed introduction: https://codeforces.me/blog/entry/118679

Register a new team: https://ucup.ac/register (the registration request will be processed before each stage)

Results of the past stages: https://ucup.ac/results

Terms: https://ucup.ac/terms

Ratings: https://ucup.ac/rating

The 1st Universal Cup. Stage 1: Shenyang (Based on The 2022 ICPC Asia Shenyang Regional Contest)

#include <bits/stdc++.h>
using namespace std;

int t, a, b, c, d;

int main() {
    for (cin >> t; t; t--) {
        cin >> a >> b >> c >> d;
        cout << b << " " << c << " " << c << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
int x,n,m,t;
void solve(){
	scanf("%d%d%d",&x,&n,&m);
	while (x>0&&n&&x/2+10<x){n--;x=x/2+10;}
	if (x<=m*10)printf("YES\n");
	else printf("NO\n"); 
}
int main(){
	scanf("%d",&t);
	while(t--)solve();
	return 0;
}

#include <bits/stdc++.h>
#define maxn 200005
std::vector<int>conj[maxn];
int n,k,u,v,depth[maxn]={0},size[maxn]={0},det[maxn];
long long ans=0;
int cmp(int a,int b){return a>b;}
int dfs(int u,int f){depth[u]=depth[f]+1;size[u]=1;
	for (int i=0;i<conj[u].size();++i){
		if ((v=conj[u][i])==f)continue;
		size[u]+=dfs(v,u);
	}det[u]=size[u]-depth[u];return size[u];
}
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1;i<n;++i){
		scanf("%d%d",&u,&v);conj[u].push_back(v);conj[v].push_back(u);
	}dfs(1,0);
	std::nth_element(det+1,det+n-k,det+n+1,cmp);
	for (int i=1;i<=n-k;++i)ans+=det[i];std::cout<<ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int t, nr, ng, nb;
long long ans;

long long sq(int x) { return 1ll * x * x; }

void solve(vector<int> a, vector<int> b, vector<int> c) {
    for (auto x : a) {
        auto y = lower_bound(b.begin(), b.end(), x);
        auto z = upper_bound(c.begin(), c.end(), x);
        if (y == b.end() || z == c.begin()) { continue; }
        z--; ans = min(ans, sq(x - *y) + sq(*y - *z) + sq(*z - x));
    }
}

int main() {
    for (cin >> t; t; t--) {
        cin >> nr >> ng >> nb;
        vector<int> r(nr), g(ng), b(nb);
        for (int i = 0; i < nr; i++) { cin >> r[i]; }
        for (int i = 0; i < ng; i++) { cin >> g[i]; }
        for (int i = 0; i < nb; i++) { cin >> b[i]; }
        sort(r.begin(), r.end());
        sort(g.begin(), g.end());
        sort(b.begin(), b.end());
        ans = 9e18;
        solve(r, g, b); solve(r, b, g);
        solve(g, b, r); solve(g, r, b);
        solve(b, r, g); solve(b, g, r);
        cout << ans << endl;
    }
    return 0;
}

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int mod = 998244353;

int main()
{
	string s, t;
	
	cin >> s >> t;
	int n = s.size();
	int m = t.size();
	
	vector<vector<int> > f(n + 1, vector<int>(m + 1));
	
	f[n][0] = 1;
	
	for (int i = n - 1; i >= 1; --i)
	{
		for (int j = 0; j <= m; ++j)
		{
			if (j == 0)
			{
				if (i >= m) f[i][0] = n - i + 1;
				else if (s[i] == t[i]) f[i][0] = f[i + 1][0];
			}
			else if (j == m)
			{
				f[i][m] = 2 * f[i + 1][m] % mod;
				if (s[i] == t[m - 1]) f[i][m] = (f[i][m] + f[i + 1][m - 1]) % mod;
			}
			else
			{
				if (i + j >= m || s[i] == t[i + j]) f[i][j] = f[i + 1][j];
				if (s[i] == t[j - 1]) f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod;
			}
		}
	}
	
	int ans = f[1][m];
	for (int i = 0; i < m; ++i) if (t[i] == s[0]) ans = (ans + f[1][i]) % mod;
	ans = ans * 2 % mod;
	
	cout << ans;
	
	return 0;
}

PinkRabbitAFO gives another solution which inserts tiles with value $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$n-1$$$, $$$1$$$ in order. See more details here.

#include <bits/stdc++.h>
using namespace std;

int n, s1, s2, t1, t2, d1[105], d2[105], a[105];

int main() {
    cin >> n >> s1 >> s2;
    for (int i = n - 1; i >= 0; i--) {
        cout << "+ " << (i > 2 ? i : i % 2 + 1) << endl;
        t1 = s1; t2 = s2; cin >> s1 >> s2;
        d1[i] = s1 - t1; d2[i] = s2 - t2;
    }
    a[1] = sqrt(d1[0] * 2);
    a[3] = d2[0] - d2[2] - 1;
    a[2] = d2[2] / (a[3] + 1);
    a[4] = d2[1] / (a[3] + 1) - a[1] - 2;
    for (int i = 5; i <= n; i++) {
        a[i] = (d2[i - 2] - a[i - 4] * a[i - 3]) / (a[i - 1] + 1) - a[i - 3] - 1;
    }
    cout << "!"; a[n]++;
    for (int i = 1; i <= n; i++) { cout << " " << a[i]; }
    cout << endl;
    return 0;
}

#include <cstdio>

const int MN = 105;

int N, lstv1, lstv2, v1, v2;
int dv1[MN], dv2[MN], Tag[MN], Ans[MN];

int main() {
	scanf("%d", &N);
	scanf("%d%d", &lstv1, &lstv2);
	for (int i = 1; i < N; ++i) {
		printf("+ %d\n", i), fflush(stdout);
		scanf("%d%d", &v1, &v2);
		dv1[i] = v1 - lstv1, dv2[i] = v2 - lstv2;
		if (dv1[i] > 0)
			for (int x = 2; x <= N; ++x)
				if (x * (x - 1) / 2 == dv1[i]) {
					Tag[i] = x; break;
				}
		lstv1 = v1, lstv2 = v2;
	}
	printf("+ 1\n"), fflush(stdout);
	scanf("%d%d", &v1, &v2);
	int ndv1 = v1 - lstv1, ndv2 = v2 - lstv2;
	for (int x = 0; x <= N; ++x)
		if (x * (x + 1) / 2 == ndv1) {
			Ans[1] = x; break;
		}
	int delta = ndv2 - dv2[1] - 1; // delta = a[2] + a[3]
	if (Tag[2] >= 2) Ans[2] = Tag[2], Ans[3] = delta - Ans[2];
	else if (Tag[3] >= 2) Ans[3] = Tag[3], Ans[2] = delta - Ans[3];
	else if (delta == 0) Ans[3] = Ans[2] = 0;
	else if (delta == 2) Ans[3] = Ans[2] = 1;
	else if (dv2[2] > 0) Ans[2] = 0, Ans[3] = 1;
	else Ans[2] = 1, Ans[3] = 0;
	for (int i = 3; i <= N - 2; ++i) {
		if (Tag[i + 1] >= 2) {
			Ans[i + 1] = Tag[i + 1];
			continue;
		}
		if ((Ans[i - 2] + 1) * (Ans[i - 1] + 1) == dv2[i]) Ans[i + 1] = 0;
		else Ans[i + 1] = 1;
	}
	Ans[N] = (dv2[N - 1] - (Ans[N - 3] + 1) * (Ans[N - 2] + 1)) / (Ans[N - 2] + 1);
	printf("!");
	for (int i = 1; i <= N; ++i) printf(" %d", Ans[i]);
	puts(""), fflush(stdout);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353, inv2 = 499122177;
const int M = 64;

int n, m, k, p[M], c[M][M];
long long a[M], b[M], f[M];

void dfs(int i, long long x) {
    if (i == k) { p[__builtin_popcountll(x)]++; return; }
    dfs(i + 1, x); dfs(i + 1, x ^ a[i]);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        for (int j = m; j >= 0; j--) {
            if (x >> j & 1) {
                if (!f[j]) { f[j] = x; break; }
                x ^= f[j];
            }
        }
    }
    for (int i = 0; i < m; i++) {
        if (f[i]) {
            for (int j = 0; j < i; j++) {
                if (f[i] >> j & 1) { f[i] ^= f[j]; }
            }
            for (int j = 0; j < m; j++) {
                if (!f[j]) { a[k] = a[k] * 2 + (f[i] >> j & 1); }
            }
            a[k] |= 1ll << m - 1 - k; k++;
        }
    }
    if (k <= 26) {
        dfs(0, 0);
        for (int i = 0; i <= m; i++) {
            int ans = p[i];
            for (int j = 0; j < n - k; j++) { ans = ans * 2 % mod; }
            cout << ans << " ";
        }
    } else {
        k = m - k; swap(a, b);
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < m - k; j++) {
                if (b[j] >> i & 1) { a[i] |= 1ll << j; }
            }
            a[i] |= 1ll << m - 1 - i;
        }
        dfs(0, 0);
        for (int i = 0; i <= m; i++) {
            c[i][0] = 1;
            for (int j = 1; j <= i; j++) { c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; }
        }
        for (int i = 0; i <= m; i++) {
            int ans = 0;
            for (int j = 0; j <= m; j++) {
                int coef = 0;
                for (int k = 0; k <= i; k++) {
                    coef = (coef + (k & 1 ? -1ll : 1ll) * c[j][k] * c[m - j][i - k] % mod + mod) % mod;
                }
                ans = (ans + 1ll * coef * p[j]) % mod;
            }
            for (int j = 0; j < k; j++) { ans = 1ll * ans * inv2 % mod; }
            for (int j = 0; j < n - m + k; j++) { ans = ans * 2 % mod; }
            cout << ans << " ";
        }
    }
    return 0;
}

Solve the same problem with $$$m \le 63$$$.

First, let's choose an arbitrary root for the tree. Then for all pairs of paths, their LCA (lowest common ancestor) can be either different or the same.

Then, let's calculate the answer of pairs with different LCAs. In this case, if the intersection is not empty, it will be a vertical path as in the graph below.

Here path $$$G-H$$$ and path $$$E-F$$$ intersects at path $$$B-G$$$.

We can process all paths in decreasing order of the depth of their LCA. When processing a path $$$p$$$ we calculate the number of paths $$$q$$$, where $$$q$$$ is processed before $$$p$$$, and the edge-intersection of $$$p$$$ and $$$q$$$ is at least $$$k$$$. To do this we can plus one to the subtree of the nodes on the path $$$k$$$ edges away from the LCA (node $$$C$$$ and $$$D$$$ for path $$$G-H$$$ in the graph above), then we can query the value at the endpoints of the path (node $$$E$$$ and $$$F$$$ for path $$$E-F$$$). We can maintain this easily with BIT (binary indexed tree, or Fenwick tree).

Next, we calculate pairs with the same LCA. This case is harder.

For each node $$$u$$$ we calculate the number of pairs with the LCA $$$u$$$.

For a pair of path $$$(x_1,y_1)$$$ and $$$(x_2, y_2)$$$, there are still two cases we need to handle.

Let $$$dfn_x$$$ be the index of $$$x$$$ in the DFS order. For a path $$$(x,y)$$$ we assume that $$$dfn_x < dfn_y$$$ (otherwise you can just swap them)

In the first case ( the right one in the graph above, where $$$(x_1,y_1) = (B,E), (x_2,y_2) = (C,F)$$$ ), the intersection of $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is the path that goes from $$$\operatorname{LCA}(x_1,x_2)$$$ to $$$\operatorname{LCA}(y_1,y_2)$$$ (path $$$A - D$$$)

In this case the intersection may cross over node $$$u$$$.

For all paths $$$(x,y)$$$ with the LCA $$$u$$$. We can build a virtual-tree over all $$$x$$$ of the paths, and on node $$$x$$$ we store the value of $$$y$$$. Let's do a dfs on the virtual-tree. On each node $$$a$$$ we calculate pairs $$$(x_1,y_1)$$$,$$$(x_2,y_2)$$$ that $$$\operatorname{LCA}(x_1,x_2) = a$$$. For $$$x_1$$$ , let's go from $$$a$$$ to $$$y_1$$$ for $$$k$$$ edges, assume the node we reached is $$$b$$$, all legal $$$y_2$$$ should be in the subtree of $$$b$$$.

We can use a segment tree on the DFS-order to maintain all $$$y$$$s in the subtree and merge them with the small-to-large trick, meanwhile, iterate over all $$$x_1$$$ in the smaller segment tree, count the valid $$$y_2$$$'s in the larger segment tree.

In fact, you can use HLD (heavy-light decomposition) instead of virtual-tree, which seems to be easier to implement.

Now note that the solution above is based on the fact that the intersection of $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is the path that goes from $$$\operatorname{LCA}(x_1,x_2)$$$ to $$$\operatorname{LCA}(y_1,y_2)$$$. But it is not always true, so here we have another case to handle.

In this case, (the left one in the graph above), the intersection is definitely a vertical path that goes from $$$u$$$ to $$$\operatorname{LCA(y_1,x_2)}$$$. This can be solved similarly to the case of different LCAs.

The overall complexity of this solution is $$$O(m \log^2 m + n\log n)$$$.

#include <bits/stdc++.h>
#define maxn 200005
int n,m,k,u[maxn],v[maxn],ch[maxn<<6][2]={0},sum[maxn<<6]={0},pt[maxn],head[maxn]={0},tail=0,cnt=0,root[maxn]={0},
anc[maxn][19]={0},son[maxn]={0},depth[maxn]={0},dfn[maxn],size[maxn],idx=0;
long long ans=0;
std::vector<int>in[maxn],vec[maxn];
struct edge {
	int v,next;
}edges[maxn<<1];
void add_edge(int u,int v){
	edges[++tail].v=v;
	edges[tail].next=head[u];
	head[u]=tail;
}
namespace BIT {
	int sum[maxn<<2]={0};
	void add(int p,int x) {if (p==0) return;while (p<=n) {sum[p]+=x;p+=p&-p;}}
	int query(int p) {int ans=0;while (p>0) {ans+=sum[p];p-=p&-p;}return ans;}
	void Add(int l,int r){add(l,1);add(r+1,-1);}
}
void update(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]];}
int insert(int rt,int l,int r,int p){
	if (!rt) rt=++cnt;
	if (l==r) {sum[rt]++;return rt;}
	int mid=(l+r)>>1;
	if (p<=mid) ch[rt][0]=insert(ch[rt][0],l,mid,p);
	else ch[rt][1]=insert(ch[rt][1],mid+1,r,p);
	update(rt);
	return rt;
} int merge(int u,int v){
	if (!u||!v)return u+v;
	ch[u][0]=merge(ch[u][0],ch[v][0]);
	ch[u][1]=merge(ch[u][1],ch[v][1]);
	sum[u]=sum[u]+sum[v];return u;
} int query(int rt,int L,int R,int l,int r){
	if (l>R||r<L)return 0;
	if (l<=L&&R<=r){return sum[rt];}
	return query(ch[rt][0],L,(L+R)>>1,l,r)+query(ch[rt][1],((L+R)>>1)+1,R,l,r);
}

void dfs1(int u,int f){
	anc[u][0]=f;depth[u]=depth[f]+1;size[u]=1;
	for (int i=1;i<=18;++i)anc[u][i]=anc[anc[u][i-1]][i-1];
	for (int i=head[u];i;i=edges[i].next){
		int v=edges[i].v;
		if (v==f) continue;
		dfs1(v,u);size[u]+=size[v];
		if (size[v]>size[son[u]])son[u]=v;
	}
} void dfsn(int u){
	dfn[u]=++idx;
	for (int i=head[u];i;i=edges[i].next){
		int v=edges[i].v;
		if (v==son[u]||v==anc[u][0])continue;
		dfsn(v);
	}if (son[u]) dfsn(son[u]);
}

int lift(int u,int x){
	for (int i=18;i>=0;i--)if (x>=(1<<i)) {u=anc[u][i];x-=(1<<i);}
	return u;
}

int lca(int u,int v){
	if (depth[u]<depth[v])std::swap(u,v);
	for (int i=18;i>=0;i--)if (depth[anc[u][i]]>=depth[v])u=anc[u][i];
	if (u==v)return u;
	for (int i=18;i>=0;i--)if (anc[u][i]!=anc[v][i]){u=anc[u][i];v=anc[v][i];}
	return anc[u][0];
} 

void dfs3(int x,int rt){
	pt[x]=x;root[x]=0;
	for (int i=0;i<in[x].size();++i) {
		int d=in[x][i];
		int rd=std::max(0,k-(depth[u[d]]-depth[rt]));
		if (depth[v[d]]-depth[rt]>=rd){
			int l=lift(v[d],depth[v[d]]-depth[rt]-rd);
			ans+=query(root[x],1,n,dfn[l],dfn[l]+size[l]-1);
		}root[x]=insert(root[x],1,n,dfn[v[d]]);
	}for (int i=head[x];i;i=edges[i].next){
		int t=edges[i].v;
		if (t==anc[x][0]||(rt==x&&t==son[x])) continue;
		dfs3(t,rt);
		if (in[pt[x]].size()<in[pt[t]].size()){
			std::swap(pt[x],pt[t]);
			std::swap(root[x],root[t]);
		}while (!in[pt[t]].empty()){
			int d=in[pt[t]][in[pt[t]].size()-1];in[pt[t]].pop_back();
			int rd=std::max(0,k-(depth[x]-depth[rt]));
			if (depth[v[d]]-depth[rt]>=rd) {
				int l=lift(v[d],(depth[v[d]]-depth[rt]-rd));
				ans+=query(root[x],1,n,dfn[l],dfn[l]+size[l]-1);
			}in[pt[x]].push_back(d);
		}root[x]=merge(root[x],root[t]);
	}
}

void dfs2(int x){
	int len=vec[x].size();
	for (int i=head[x];i;i=edges[i].next)if (edges[i].v!=anc[x][0])dfs2(edges[i].v);
	for (int i=0;i<len;++i)ans+=BIT::query(dfn[v[vec[x][i]]]);
	for (int i=0;i<len;++i){
		int j=vec[x][i];
		if (depth[v[j]]-depth[x]>=k) {
			int l=lift(v[j],depth[v[j]]-depth[x]-k);
			BIT::Add(dfn[l],dfn[l]+size[l]-1);
		}
	}for (int i=0;i<len;++i){ans+=BIT::query(dfn[u[vec[x][i]]]);in[u[vec[x][i]]].push_back(vec[x][i]);}
	dfs3(x,x);
	while (!in[pt[x]].empty())in[pt[x]].pop_back();
	for (int i=0;i<len;++i){
		int j=vec[x][i];
		if (depth[u[j]]-depth[x]>=k) {
			int l=lift(u[j],depth[u[j]]-depth[x]-k);
			BIT::Add(dfn[l],dfn[l]+size[l]-1);
		}
	}
}
	
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);
		add_edge(v,u);
	}dfs1(1,0);dfsn(1);
	for (int i=1;i<=m;++i){
		scanf("%d%d",&u[i],&v[i]);
		if (dfn[u[i]]>dfn[v[i]]) std::swap(u[i],v[i]);
		int l=lca(u[i],v[i]);
		vec[l].push_back(i);
	} dfs2(1);
	std::cout<<ans;
	return 0;
}