Codeforces Round #810 Editorial

Revision en9, by Rhodoks, 2022-07-25 12:05:21

Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask.

1711A - Совершенная перестановка

hint1.
solution
code

1711B - Вечеринка

hint1.
hint2.
solution
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
int x[MAXN],y[MAXN],a[MAXN],degree[MAXN];
int n,m;
void work()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		degree[i]=0;
		cin>>a[i];
	}
	for (int i=1;i<=m;i++)
	{
		cin>>x[i]>>y[i];
		degree[x[i]]++;
		degree[y[i]]++;
	}
	int ans=INT_MAX;
	if (m%2==0)
		ans=0;
	for (int i=1;i<=n;i++)
		if (degree[i]%2==1)
			ans=min(ans,a[i]);
	for (int i=1;i<=m;i++)
		if (degree[x[i]]%2==0 && degree[y[i]]%2==0)
			ans=min(ans,a[x[i]]+a[y[i]]);
	cout<<ans<<endl;
}

int main()
{
	int casenum=1;
	cin>>casenum;
	for (int testcase=1;testcase<=casenum;testcase++)
		work();
	return 0;
}

1710A - Покраска рисунка

hint1.
hint2.
solution
code

1710B - Дождь

hint1.
hint2.
hint3.
solution
code

1710C - XOR-треугольники

hint1.
hint2.
solution
code

1710D - Восстановление дерева

Thank dario2994, the key part of the proof is from him.

hint1
hint2
hint3
solution
code

1210E - Войтек и карточные фокусы

hint1.
hint2.
hint3.
solution
code

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en21 English Rhodoks 2022-07-29 17:45:36 78
en20 English Rhodoks 2022-07-29 17:37:19 125
en19 English Rhodoks 2022-07-28 05:58:51 30 Tiny change: 'en $\sum_{i=1}^{n} \lfloor ' -> 'en $\sum_{a_i \geq 2*m} \lfloor '
en18 English Rhodoks 2022-07-26 07:56:12 0 (published)
en17 English Rhodoks 2022-07-26 07:53:05 261 (saved to drafts)
en16 English Rhodoks 2022-07-25 13:31:12 14 Tiny change: 'ly if $p_j-|x_i-x_j| >= p_i-m$.\n\nOn' -> 'ly if $p_i-|x_i-j| \geq a_j-m$.\n\nOn'
en15 English Rhodoks 2022-07-25 12:23:12 6 Tiny change: ' then $A \union B$ is goo' -> ' then $A \cup B$ is goo'
en14 English Rhodoks 2022-07-25 12:18:19 0 (published)
en13 English Rhodoks 2022-07-25 12:13:06 70
en12 English Rhodoks 2022-07-25 12:10:10 2 Tiny change: '[problem:1210E]\n\n<s' -> '[problem:1710E]\n\n<s'
en11 English Rhodoks 2022-07-25 12:09:44 20
en10 English Rhodoks 2022-07-25 12:05:53 38
en9 English Rhodoks 2022-07-25 12:05:21 6173
en8 English Rhodoks 2022-07-25 11:55:32 6538
en7 English Rhodoks 2022-07-25 11:44:35 1023
en6 English Rhodoks 2022-07-25 11:18:49 205
en5 English Rhodoks 2022-07-25 11:14:54 3601 Tiny change: 't \cup I_i¥\n\n</spoi' -> 't \cup I_i\n\n</spoi'
en4 English Rhodoks 2022-07-25 00:37:54 23
en3 English Rhodoks 2022-07-25 00:28:39 1761
en2 English Rhodoks 2022-07-25 00:24:26 1933
en1 English Rhodoks 2022-07-25 00:21:28 1379 Initial revision (saved to drafts)