Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#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()
#define all(v) v.begin(),v.end()
#define eb emplace_back
void solve() {
int m; cin >> m;
string t = to_string(m);
string s = "1";
for (int i = 1; i < sz(t); i++) {
s += '0';
}
int k = stoi(s);
cout << m - k << '\n';
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
1702B - Polycarp Writes a String from Memory
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#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()
#define all(v) v.begin(),v.end()
#define eb emplace_back
void solve() {
string s; cin >> s;
set<char> v;
int ans = 0;
for (int i = 0; i < sz(s); i++) {
v.insert(s[i]);
if (sz(v) > 3) {
ans++;
v.clear();
v.insert(s[i]);
}
}
if (!v.empty()) ans++;
cout << ans << endl;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
void solve(){
int n, k;
cin >> n >> k;
map<int, pair<int, int>>m;
forn(i, n){
int u;
cin >> u;
if(!m.count(u)) {
m[u].first = i;
m[u].second = i;
}
else m[u].second = i;
}
forn(i, k){
int a, b;
cin >> a >> b;
if(!m.count(a) or !m.count(b) or m[a].first > m[b].second) {
cout << "NO\n"; //equals = 0 = wrong
}
else cout << "YES\n";
}
}
int main(){
int t;
cin >> t;
while(t--){
solve();
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#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) {
string s;
cin >> s;
int p;
cin >> p;
string w(s);
sort(w.rbegin(), w.rend());
int cost = 0;
forn(i, s.length())
cost += s[i] - 'a' + 1;
map<char,int> del;
forn(i, w.length())
if (cost > p) {
del[w[i]]++;
cost -= w[i] - 'a' + 1;
}
forn(i, s.length()) {
if (del[s[i]] > 0) {
del[s[i]]--;
continue;
}
cout << s[i];
}
cout << endl;
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); i++)
map<int, vector<int>> m;
vector<bool> used;
int go(int v) {
used[v] = true;
for (auto now : m[v]) {
if (!used[now]) {
return go(now) + 1;
}
}
return 1;
}
void solve() {
int n, x, y;
cin >> n;
m.clear();
used.clear();
used.resize(n + 1, false);
bool fault = false;
forn(i, n) {
cin >> x >> y;
m[x].push_back(y);
m[y].push_back(x);
if (x == y || m[x].size() > 2 || m[y].size() > 2) fault = true;
}
if (fault) {
cout << "NO\n";
return;
}
forn(i, n) {
if (!used[i + 1]) {
if (go(i + 1) % 2) {
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
}
int main() {
int tests;
cin >> tests;
forn(tt, tests) {
solve();
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#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()
#define all(v) v.begin(),v.end()
#define eb emplace_back
const int INF = 1e9;
void solve() {
int n; cin >> n;
multiset<int> a, b;
forn(i, n) {
int x; cin >> x;
while (x % 2 == 0) {
x /= 2;
}
a.insert(x);
}
forn(i, n) {
int x; cin >> x;
b.insert(x);
}
n = sz(a);
while (!b.empty()) {
int x = *b.rbegin();
// cout << x << endl;
if (!a.count(x)) {
if (x == 1) break;
b.erase(b.find(x));
b.insert(x / 2);
} else {
b.erase(b.find(x));
a.erase(a.find(x));
}
}
cout << (b.empty() ? "YES" : "NO") << endl;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
1702G1 - Passable Paths (easy version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#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 = 1e15;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
void depth(int v, int p, vector<vector<int>> &sl, vector<int> &d){
if(p >= 0) d[v] = d[p] + 1;
for(int u: sl[v]){
if(u == p) continue;
depth(u, v, sl, d);
}
}
int dfs(int v, int p, vector<vector<int>> &sl, vector<bool> &chosen){
int res = 0;
bool lower = false;
for(int u: sl[v]){
if(u == p) continue;
res += dfs(u, v, sl, chosen);
lower = lower || chosen[u];
}
chosen[v] = chosen[v] || lower;
if(chosen[v] && !lower) res = 1;
return res;
}
void solve(){
int n;
cin >> n;
vector<vector<int>> sl(n);
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
sl[--u].push_back(--v);
sl[v].push_back(u);
}
vector<int> d(n);
depth(0, -1, sl, d);
int q;
cin >> q;
for(; q; --q){
int k;
cin >> k;
vector<bool> chosen(n);
int mx = 0;
for(int i = 0; i < k; ++i){
int p;
cin >> p;
--p;
if(d[p] > d[mx]) mx = p;
chosen[p] = true;
}
int leaves = dfs(mx, -1, sl, chosen);
if(leaves == 1) cout << "YES\n";
else cout << "NO\n";
}
}
bool multi = false;
signed main() {
int t = 1;
if (multi)cin >> t;
for (; t; --t) {
solve();
//cout << endl;
}
return 0;
}
1702G2 - Passable Paths (hard version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#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 = 1e15;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
int n, sz;
vector<vector<int>> sl, up;
vector<int> d;
void precalc(int v, int p){
d[v] = d[p] + 1;
up[v][0] = p;
for(int i = 1; i <= sz; ++i){
up[v][i] = up[up[v][i - 1]][i - 1];
}
for(int u: sl[v]){
if(u == p) continue;
precalc(u, v);
}
}
int lca(int u, int v){
if(d[u] < d[v]){
swap(u, v);
}
for(int cur = sz; cur >= 0; --cur){
if (d[u] - (1 << cur) >= d[v]) {
u = up[u][cur];
}
}
for(int cur = sz; cur >= 0; --cur){
if (up[u][cur] != up[v][cur]) {
u = up[u][cur];
v = up[v][cur];
}
}
return u == v ? u : up[u][0];
}
void solve(){
cin >> n;
sz = 0;
while ((1 << sz) < n) sz++;
d.assign(n, -1);
up.assign(n, vector<int>(sz + 1));
sl.assign(n, vector<int>(0));
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
sl[--u].push_back(--v);
sl[v].push_back(u);
}
precalc(0, 0);
int q;
cin >> q;
for(; q; --q){
int k;
cin >> k;
vector<int> p(k);
for(int &e: p) {
cin >> e;
--e;
}
sort(all(p), [](int a, int b) {
return d[a] > d[b];
});
vector<bool> used(k);
for(int i = 0; i < k; ++i){
if(lca(p[0], p[i]) == p[i]) used[i] = true;
}
int f = 0;
while (f < k && used[f]) f++;
if(f == k){
cout << "YES\n";
continue;
}
bool ans = true;
for(int i = f; i < k; ++i){
if(lca(p[f], p[i]) == p[i]) used[i] = true;
}
for(bool e: used){
ans &= e;
}
ans &= d[lca(p[0], p[f])] <= d[p.back()];
if(ans) cout << "YES\n";
else cout << "NO\n";
}
}
bool multi = false;
signed main() {
int t = 1;
if (multi)cin >> t;
for (; t; --t) {
solve();
//cout << endl;
}
return 0;
}