↵
Идея: [user:MisterGu,2021-11-26]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1611A]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
int t;↵
cin >> t;↵
while(t--) {↵
string n;↵
cin >> n;↵
if((n.back() - '0') % 2 == 0) {↵
cout << "0\n";↵
continue;↵
}↵
if((n[0] - '0') % 2 == 0) {↵
cout << "1\n";↵
continue;↵
}↵
int count_2 = count(n.begin(), n.end(), '2');↵
int count_4 = count(n.begin(), n.end(), '4');↵
int count_6 = count(n.begin(), n.end(), '6');↵
int count_8 = count(n.begin(), n.end(), '8');↵
if(count_2 > 0 || count_4 > 0 || count_6 > 0 || count_8 > 0) {↵
cout << "2\n";↵
continue;↵
}↵
cout << "-1\n";↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1611B]↵
↵
Идея: [user:MikeMirzayanov,2021-11-26]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1611B]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
void solve() {↵
ll a, b;↵
cin >> a >> b;↵
cout << min(min(a, b), (a + b) / 4) << '\n';↵
}↵
↵
int main() {↵
int t;↵
cin >> t;↵
for (int i = 0; i < t; ++i) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1611C]↵
↵
Идея: [user:MikeMirzayanov,2021-11-26]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1611C]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
↵
int main() {↵
int t;↵
cin >> t;↵
forn(tt, t) {↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
forn(i, n)↵
cin >> a[i];↵
if (a[0] != n && a[n - 1] != n)↵
cout << -1 << endl;↵
else {↵
for (int i = n - 1; i >= 0; i--)↵
cout << a[i] << " ";↵
cout << endl;↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1611D]↵
↵
Идея: [user:MikeMirzayanov,2021-11-26]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1611D]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
void solve(){↵
int n;↵
cin >> n;↵
vector<int> b(n + 1), p(n + 1), dist(n + 1, -1);↵
↵
for(int i = 1; i <= n; i++)↵
cin >> b[i];↵
for(int i = 1; i <= n; i++)↵
cin >> p[i];↵
↵
if (b[p[1]] != p[1]){↵
cout << -1 << '\n';↵
return;↵
}↵
↵
dist[p[1]] = 0;↵
for(int i = 2; i <= n; i++){↵
if(dist[b[p[i]]] == -1){↵
cout << -1 << '\n';↵
return;↵
}↵
dist[p[i]] = dist[p[i - 1]] + 1;↵
}↵
↵
for(int i = 1; i <= n; i++) {↵
cout << dist[i] - dist[b[i]] << ' ';↵
}↵
cout << '\n';↵
}↵
↵
int main() {↵
int t;↵
cin >> t;↵
while(t-- > 0) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1611E1]↵
↵
Идея: [user:Vladosiya,2021-11-26]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1611E1]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
//↵
// Created by Vlad on 16.11.2021.↵
//↵
↵
#include <bits/stdc++.h>↵
↵
#define int long long↵
#define mp make_pair↵
#define x first↵
#define y second↵
#define all(a) (a).begin(), (a).end()↵
#define rall(a) (a).rbegin(), (a).rend()↵
↵
typedef long double ld;↵
typedef long long ll;↵
↵
using namespace std;↵
↵
mt19937 rnd(143);↵
↵
const int inf = 1e10;↵
const int M = 998244353;↵
const ld pi = atan2(0, -1);↵
const ld eps = 1e-4;↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
vector<int> color(n, -1);↵
deque<int> q;↵
for(int i = 0; i < k; ++i){↵
int x;↵
cin >> x;↵
color[--x] = 0;↵
q.push_back(x);↵
}↵
color[0] = 1;↵
q.push_back(0);↵
vector<vector<int>> g(n);↵
for(int i = 0; i < n - 1; ++i){↵
int u, v;↵
cin >> u >> v;↵
g[--u].push_back(--v);↵
g[v].push_back(u);↵
}↵
while(!q.empty()){↵
int v = q.front();↵
q.pop_front();↵
for(int u: g[v]){↵
if(color[u] == -1){↵
color[u] = color[v];↵
q.push_back(u);↵
}↵
}↵
}↵
for(int v = 1; v < n; ++v){↵
if(g[v].size() == 1 && color[v] == 1){↵
cout << "YES";↵
return;↵
}↵
}↵
cout << "NO";↵
}↵
↵
bool multi = true;↵
↵
signed main() {↵
int t = 1;↵
if (multi) {↵
cin >> t;↵
}↵
for (; t != 0; --t) {↵
solve();↵
cout << "\n";↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1611E2]↵
↵
Идея: [user:Vladosiya,2021-11-26]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1611E2]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define int long long↵
#define mp make_pair↵
#define x first↵
#define y second↵
#define all(a) (a).begin(), (a).end()↵
#define rall(a) (a).rbegin(), (a).rend()↵
↵
/*#pragma GCC optimize("Ofast")↵
#pragma GCC optimize("no-stack-protector")↵
#pragma GCC optimize("unroll-loops")↵
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")↵
#pragma GCC optimize("fast-math")↵
*/↵
typedef long double ld;↵
typedef long long ll;↵
↵
using namespace std;↵
↵
mt19937 rnd(143);↵
↵
const int inf = 1e10;↵
const int M = 998244353;↵
const ld pi = atan2(0, -1);↵
const ld eps = 1e-4;↵
↵
vector<vector<int>> sl;↵
vector<int> nearest;↵
↵
int count(int v, int dist, int p = -1){↵
bool children = true;↵
int s = 0;↵
for(int u: sl[v]){↵
if(u == p) continue;↵
int c = count(u, dist + 1, v);↵
if(c < 0) children = false;↵
nearest[v] = min(nearest[v], nearest[u] + 1);↵
s += c;↵
}↵
if(nearest[v] <= dist) return 1;↵
if(s == 0 || !children) return -1;↵
return s;↵
}↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
sl.assign(n, vector<int>(0));↵
nearest.assign(n, n);↵
for(int i = 0; i < k; ++i){↵
int x;↵
cin >> x;↵
--x;↵
nearest[x] = 0;↵
}↵
for(int i = 1; i < n; ++i){↵
int u, v;↵
cin >> u >> v;↵
--u, --v;↵
sl[u].emplace_back(v);↵
sl[v].emplace_back(u);↵
}↵
cout << count(0, 0);↵
}↵
↵
bool multi = true;↵
↵
signed main() {↵
//freopen("in.txt", "r", stdin);↵
//freopen("in.txt", "w", stdout);↵
/*ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);*/↵
int t = 1;↵
if (multi) {↵
cin >> t;↵
}↵
for (; t != 0; --t) {↵
solve();↵
cout << "\n";↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1611F]↵
↵
Идея: [user:Gol_D,2021-11-26], [user:MikeMirzayanov,2021-11-26]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1611F]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
↵
vector<ll> t, a;↵
ll s, tl;↵
↵
const ll MAX = 1'000'000'000'000'000LL;↵
↵
void build(int v, int l, int r) {↵
if (l == r)↵
t[v] = a[l];↵
else {↵
int m = (l + r) / 2;↵
build (v * 2, l, m);↵
build (v * 2 + 1, m + 1, r);↵
t[v] = min(t[v * 2], t[v * 2 + 1]);↵
}↵
}↵
↵
void update(int v, int l, int r) {↵
if (l == r)↵
t[v] = MAX;↵
else {↵
int m = (l + r) / 2;↵
if (tl <= m)↵
update(v * 2, l, m);↵
else↵
update(v * 2 + 1, m + 1, r);↵
t[v] = min(t[v * 2], t[v * 2 + 1]);↵
}↵
}↵
↵
int lower_bound_s(int v, int l, int r) {↵
if (r < tl || (l == r && s < -t[v])) {↵
return -1;↵
}↵
if (l == r || -t[v] <= s) {↵
return r;↵
}↵
int m = (l + r) / 2;↵
↵
if (m < tl) {↵
return lower_bound_s(2 * v + 1, m + 1, r);↵
}↵
if (s < -t[2 * v]) {↵
return lower_bound_s(2 * v, l, m);↵
}↵
int res = lower_bound_s(2 * v + 1, m + 1, r);↵
return (res == -1) ? m : res;↵
}↵
↵
↵
int main() {↵
int tests;↵
cin >> tests;↵
forn(tt, tests) {↵
int n;↵
cin >> n >> s;↵
t = vector<ll>(4 * n);↵
a = vector<ll>(n);↵
forn(i, n) {↵
cin >> a[i];↵
}↵
for (int i = 1; i < n; ++i) {↵
a[i] += a[i - 1];↵
}↵
build(1, 0, n - 1);↵
int first = -1, second = -2;↵
for (tl = 0; tl < n; ++tl) {↵
int v = lower_bound_s(1, 0, n - 1);↵
if (v != -1 && v - tl > second - first) {↵
first = tl + 1;↵
second = v + 1;↵
}↵
s -= a[tl];↵
if (tl != 0) s += a[tl - 1];↵
update(1, 0, n - 1);↵
}↵
if (first == -1) {↵
cout << -1;↵
} else {↵
cout << first << " " << second;↵
}↵
cout << endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1611G]↵
↵
Идея: [user:MikeMirzayanov,2021-11-26]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1611G]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
#define sz(v) (int)v.size()↵
↵
const int N = 1e6 + 50;↵
string a[N];↵
↵
int n,m;↵
int ans;↵
↵
void solve(int sum0) {↵
vector<int> v;↵
for (int sum = sum0, ad = 0, pref = 0; sum < n + m; sum += 2, ad++) {↵
vector<int> cur;↵
int li = max(0, sum - m + 1), ri = min(n - 1, sum);↵
if (li > ri) continue;↵
↵
for (int i = li; i <= ri; i++) {↵
int j = sum - i;↵
↵
if (a[i][j] == '1')↵
cur.emplace_back(i);↵
}↵
↵
while (pref != sz(v) && v[pref] + ad > ri) {↵
pref++;↵
}↵
for (int i = pref; i < sz(v); i++) {↵
int new_val = v[i];↵
while (!cur.empty() && cur.back() - ad >= v[i]) {↵
new_val = max(new_val, cur.back() - ad);↵
cur.pop_back();↵
}↵
v[i] = new_val;↵
}↵
if (!cur.empty()) {↵
v.emplace_back(cur.back() - ad);↵
ans++;↵
}↵
}↵
}↵
↵
int main() {↵
int t;↵
cin >> t;↵
↵
forn(tt, t) {↵
cin >> n >> m;↵
↵
forn(i, n) {↵
string s; ↵
cin >> a[i];↵
}↵
↵
ans = 0;↵
solve(0);↵
solve(1);↵
↵
cout << ans << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
