Inspired by ivan100sic's [problem list blog](https://codeforces.net/blog/entry/98630), I'll pick 10 nontrivial-seeming recent POI (Polish Olympiad in Informatics) problems that I haven't solved and track my progress here. ↵
↵
It seems to me that POI is better suited for this format as their editorials are quite difficult to find (if possible [at all](https://szkopul.edu.pl/problemset/problem/v2Y2_UW56ENMcbwP22tkTb7a/site/?key=statement)). ↵
↵
While Ivan's original challenge was supposed to last an entire year, I'm not nearly as patient, so I won't look for editorials only until February 1st (in just over 2 weeks). Hopefully I'll have completed at least 80% by that time. Until then, GLHF!!!↵
↵
The List:↵
↵
1. [Multidrink 2013](https://szkopul.edu.pl/problemset/problem/GyDCbdIgFY5FsMa9iIsBl3hf/site/?key=statement) [Solved Jan 15]↵
↵
<spoiler summary="Fun-ness:">↵
5/10↵
↵
<spoiler summary="Comments">↵
My thought process on this problem went like "ew this is disgusting implementation" => "oh actually it's not so bad" => "oh no it's actually disgusting implementation"↵
↵
But I actually enjoyed this one more than most heavy casework/implementation problems because, while you have to be very careful about the dp transitions and especially their order, it's not too hard to prove once you have it written out. ↵
↵
<spoiler summary="my ugly code (if ppl not doing the challenge want to take a peek?)">↵
↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"BRAK\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 1e6+5;↵
↵
vector<int> pth; // path from s to t!↵
↵
int dp1[maxn], dp2[maxn]; // maximum number of free steps after {1: stomping here, 2: being here but not stomping}↵
vector<pii> run1[maxn], run2[maxn]; // for restoring answer↵
bool onpth[maxn];↵
↵
vector<pii> g[maxn]; // {to, edge id}↵
↵
bool findpth(int v, int T, int p) {↵
if (v == T) {↵
pth.pb(T); return 1;↵
}↵
for (pii u : g[v]) {↵
if (u.f != p && findpth(u.f,T,v)) {↵
pth.pb(v); onpth[u.s] = 1; return 1;↵
}↵
}↵
return 0;↵
}↵
↵
#define piii pair<pii,int>↵
↵
void dfs(int v, int par) {↵
dp2[v] = 3; // i'm so free i haven't even stomped yet↵
dp1[v] = 2; // yarrr i'm freshly stomped mmm↵
run1[v].pb({v, -1});↵
vector<piii > us;↵
for (pii p : g[v]) {↵
int u = p.f;↵
if (!onpth[p.s] && p.f != par) {↵
// tree edge!↵
dfs(u,v);↵
us.pb({{dp1[u],dp2[u]}, u});↵
}↵
}↵
↵
sort(ALL(us), [&](piii a, piii b) {↵
if (a.f.f == 2 || b.f.f == 2) return a.f.f > b.f.f; // i want to work with walking the leaf nodes first↵
if (a.f.f != b.f.f) return a.f.f > b.f.f;↵
if (a.f.f == 1) {↵
return a.f.s < b.f.s; // waste a bad dp↵
}↵
return a.f.s < b.f.s; // doesn't matter at this point ig↵
} );↵
for (auto rr : us) {↵
int u = rr.s;↵
↵
if (dp2[v] == 3){ // work with node free, this time we haven't stomped yet↵
if (dp1[u] == 2) {↵
// it's a leaf or something, anyways we can ignore it after stomping and come back↵
run2[v].pb({u,1});↵
goto dp2done;↵
}else{↵
if (dp1[u]==1) { // i stomp it and come back?↵
run2[v].pb({u,1});↵
run2[v].pb({v,-1});↵
dp2[v] = 2;↵
goto dp2done;↵
}else { // all hopeless, i have to stomp myself first↵
run2[v].pb({v,-1});↵
dp2[v] = 2;↵
}↵
}↵
}↵
if (dp2[v] == 2) {↵
// im forced to have stomped here now↵
// this will be equivalent to a later one↵
if (dp2[u] == 2) {↵
run2[v].pb({u,2});↵
dp2[v] = 1;↵
goto dp2done;↵
}else{↵
dp2[v] = 0;↵
goto dp2done;↵
}↵
}↵
if (dp2[v] == 1) {↵
if (dp1[u] == 2) {↵
run2[v].pb({u,1});↵
dp2[v] = 1;↵
goto dp2done;↵
}else{↵
dp2[v] = 0;↵
goto dp2done;↵
}↵
}↵
dp2done:;↵
}↵
sort(ALL(us), [&](piii a, piii b) {↵
return a.f.f < b.f.f; // you want to waste a bad dp1 early on↵
} );↵
for (auto rr : us) {↵
int u = rr.s;↵
↵
if (dp1[v] == 2) {↵
if (dp2[u] == 2) {↵
run1[v].pb({u,2});↵
dp1[v] = 1;↵
goto dp1done;↵
}else{↵
dp1[v] = 0;↵
goto dp1done;↵
}↵
}↵
↵
if (dp1[v] == 1) {↵
if (dp1[u] == 2) {↵
run1[v].pb({u,1});↵
dp1[v] = 1;↵
goto dp1done;↵
}else{↵
dp1[v] = 0;↵
goto dp1done;↵
}↵
}↵
↵
dp1done:;↵
↵
}↵
if (dp2[v] == 3) {↵
run2[v].pb({v, -1});↵
dp2[v] = 2;↵
} // no point in being super free now, 2 is good enough↵
assert(dp2[v] >= dp1[v]);↵
}↵
↵
vector<int> re;↵
↵
void prt(int v, int tp) {↵
if (tp == -1) {↵
re.pb(v); return;↵
}↵
for (pii p : tp==1?run1[v]:run2[v]) {↵
prt(p.f, p.s);↵
}↵
}↵
↵
signed main(){↵
IOS();↵
int n; cin>>n;↵
REP(i,n-1) {↵
int a,b; cin>>a>>b;↵
g[a].pb({b,i});↵
g[b].pb({a,i});↵
}↵
↵
findpth(1, n, -1);↵
reverse(ALL(pth));↵
↵
for (int x : pth) bug(x);↵
↵
int can = 1;↵
↵
vector<int> tp(SZ(pth));↵
↵
↵
REP(i, SZ(pth)) {↵
tp[i] = can;↵
int v = pth[i];↵
dfs(v, -1);↵
bug(v, can);↵
if (can == 0) GG();↵
if (i == SZ(pth)-1 && can == 1 && dp1[v] != 2) GG(); // can't stomp the last one first↵
bug(v, dp1[v], dp2[v]);↵
if (can == 2) {↵
can = dp2[v];↵
}else{↵
can = dp1[v];↵
}↵
}↵
bug(can);↵
if (can == 0 || can == 1) GG();↵
↵
REP(i, SZ(pth)) {↵
prt(pth[i], tp[i]);↵
}↵
↵
for (int x : re) cout<<x<<endl;↵
↵
}↵
↵
```↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
2. [Snake 2014](https://szkopul.edu.pl/problemset/problem/3zwfwt3ZGc2f6NndNgzS3Dfu/site/?key=statement)↵
3. [Arkanoid 2016](https://szkopul.edu.pl/problemset/problem/O730xgZEVynTWBmscBinhMbD/site/?key=statement) [Solved Jan 16]↵
↵
<spoiler summary="Fun-ness:">↵
4/10↵
↵
<spoiler summary="Comments">↵
↵
Another heavy implementation problem. Actually, the implementation isn't terrible (if you split the grid into 2N x 2M nodes), but I spent a long time debugging because I didn't realize that most exGCD implementations can't handle negative numbers well...↵
↵
<spoiler summary="more ugly code">↵
↵
```c↵
#include <bits/stdc++.h>↵
//#undef BALBIT↵
using namespace std;↵
#define ll long long↵
#define int ll↵
#define pii pair<int, int>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b) % mo;↵
}↵
↵
const int maxn = 1e5+5;↵
↵
int n,m,npts;↵
↵
pii flip(pii pt, pii dir) {↵
if (dir.f == -1 && pt.f) {↵
pt.f = 4*m-pt.f;↵
}↵
if (dir.s == -1 && pt.s) {↵
pt.s = 4*n-pt.s;↵
}↵
return pt;↵
}↵
↵
struct point{↵
↵
};↵
↵
vector<pair<pii, pii> > from[maxn]; // x=1 or 3, a-value↵
↵
↵
ll euclid(ll a, ll b, ll &x, ll &y) {↵
if (b) { ll d = euclid(b, a % b, y, x);↵
return y -= a/b * x, d; }↵
return x = 1, y = 0, a;↵
}↵
↵
↵
pii get(pii p) {↵
int piff = p.f - p.s; bug(piff);↵
int x = 0;↵
↵
if ((piff-1) % 4 == 0) x = 1;↵
else x = 3;↵
↵
pii k;↵
euclid(-m,n,k.f,k.s);↵
if (k.f * -m + k.s * n < 0) {↵
k.f *= -1; k.s *= -1;↵
}↵
↵
int RHS = (piff - x) / 4; assert((piff-x)%4==0);↵
↵
k.f *= RHS; k.s *= RHS;↵
↵
ll a = p.s + k.s * 4 * n; a %= (4*n*m);↵
if (a < 0) a += 4*n*m;↵
↵
bug(p.f, p.s, x, a);↵
return {x, a};↵
}↵
↵
ll smat(vector<pii> var){↵
array<set<pair<pii, pii> >, 4> s; // for the two values of x shift↵
↵
REP(i,npts) {↵
int x,y; tie(x,y) = var[i]; x*=2; y*=2; --x; --y;↵
↵
vector<pii> v;↵
vector<pii> vf;↵
if (x-1!=0){↵
// left edge↵
v.pb(flip({x-1,y}, {1,-1}));↵
v.pb(flip({x-1,y}, {1,+1}));↵
↵
vf.pb(flip({x-1,y}, {-1,-1}));↵
vf.pb(flip({x-1,y}, {-1,+1}));↵
}↵
if (x+1!=m*2){↵
// right edge↵
v.pb(flip({x+1,y}, {-1,-1}));↵
v.pb(flip({x+1,y}, {-1,+1}));↵
↵
vf.pb(flip({x+1,y}, {1,-1}));↵
vf.pb(flip({x+1,y}, {1,+1}));↵
}↵
if (y+1!=n*2){↵
// top edge↵
v.pb(flip({x,y+1}, {1,-1}));↵
v.pb(flip({x,y+1}, {-1,-1}));↵
↵
vf.pb(flip({x,y+1}, {1,1}));↵
vf.pb(flip({x,y+1}, {-1,1}));↵
}↵
if (y-1!=0){↵
// bottom edge↵
v.pb(flip({x,y-1}, { 1,+1}));↵
v.pb(flip({x,y-1}, {-1,+1}));↵
↵
vf.pb(flip({x,y-1}, { 1,-1}));↵
vf.pb(flip({x,y-1}, {-1,-1}));↵
}↵
↵
REP(j, SZ(v)) {↵
pii p = v[j];↵
pii pa = get(p);↵
int x = pa.f, a = pa.s;↵
↵
pii fop = get(vf[j]);↵
↵
from[i].pb({{a, x}, fop});↵
s[x].insert({{a, i}, fop});↵
}↵
↵
}↵
↵
pii nowdir = {-1,1};↵
pii nowpt = flip({m,0}, nowdir);↵
pii A = get(nowpt);↵
↵
bug(A.f, A.s);↵
↵
pii tmp = get(flip({m-1,1}, nowdir));↵
bug(tmp.f, tmp.s);↵
↵
ll ret = 0;↵
↵
while (SZ(s[1])) {↵
auto nxt = s[A.f].lower_bound({{A.s, -1},{-1,-1}});↵
if (nxt == s[A.f].end()) nxt = s[A.f].begin();↵
ll df = (*nxt).f.f - A.s;↵
assert(df != 0);↵
↵
if (df < 0) df += 4*n*m; // not sure, maybe 2nm??↵
ret += df;↵
↵
bug(df, ret);↵
↵
A = (*nxt).s;↵
// A = get(nowpt);↵
↵
int bye = (*nxt).f.s;↵
bug(bye);↵
for (auto p : from[bye]) {↵
int X = p.f.s;↵
p.f.s = bye;↵
s[X].erase(p);↵
}↵
}↵
↵
return ret;↵
}↵
↵
int yo[500][500];↵
↵
ll dumb(vector<pii> var) {↵
int i =0;↵
for (pii p : var) {↵
int x = p.f, y = p.s; x = x*2-1; y = y*2-1;↵
yo[x+1][y]++;↵
yo[x][y+1]++;↵
yo[x-1][y]++;↵
yo[x][y-1]++;↵
yo[x][y]=1;↵
++i;↵
}↵
int x = m, y = 0;↵
int dx = -1, dy = 1;↵
int bar = 0;↵
int re = 0;↵
while (bar < npts) {↵
x += dx; y += dy; ++re;↵
↵
pii tmp = get(flip({x,y}, {dx, dy}));↵
↵
bug(x,y,re,tmp.f, tmp.s);↵
if (yo[x][y]) {↵
// bump!↵
REP(ss, 4){↵
int tx = (ss-1)%2; // -1 0 1 0↵
int ty = (2-ss)%2; // 0 1 0 -1↵
if (yo[tx+x][ty+y]) {↵
int X = tx+x, Y = ty+y;↵
↵
if (tx) dx *= -1;↵
else dy *= -1;↵
↵
for (int sx:{-1,1}) for (int sy:{-1,1}) {↵
--yo[X+sx][Y+sy];↵
}↵
yo[X][Y] = 0;↵
goto yar;↵
}↵
}↵
↵
yar:;↵
↵
++bar;↵
}else{↵
if (x == 0 || x == 2*m) dx *= -1;↵
if (y == 0 || y == 2*n) dy *= -1;↵
}↵
}↵
return re;↵
}↵
↵
signed main(){↵
IOS();↵
cin>>m>>n>>npts; // m is for X, n is for Y↵
↵
vector<pii> var;↵
REP(i,npts) {↵
int x,y; cin>>x>>y; var.pb({x,y});↵
}↵
↵
cout<< smat(var)<<endl;↵
↵
// ll poo = dumb(var);↵
↵
// bug(ss, poo);↵
↵
}↵
```↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
↵
↵
4. [Strikes 2017](https://szkopul.edu.pl/problemset/problem/lR_LabSUC2n7EMmDHpw-wk_b/site/?key=statement) [Solved Jan 16]↵
↵
<spoiler summary="Oops">↵
Oops, I accidentally slipped a trivial one in this list X_X↵
↵
I thought it was ~80 solves in the first round but it turned out to be ~80 solves in the second round haha↵
↵
I'll add direction signs to the list to compensate for this one↵
↵
<spoiler summary="code :/">↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 5e5+5;↵
↵
vector<int> g[maxn];↵
int par[maxn];↵
int ch[maxn]; // number of white children↵
bool black[maxn];↵
↵
void dfs(int v, int p) {↵
par[v] = p;↵
for (int u : g[v]) {↵
if (u != p) {↵
dfs(u,v);↵
++ch[v];↵
}↵
}↵
}↵
↵
signed main(){↵
IOS();↵
↵
int n; cin>>n;↵
REP(i,n-1) {↵
int a,b; cin>>a>>b;↵
g[a].pb(b); g[b].pb(a);↵
}↵
dfs(1,-1);↵
↵
int V = n; int E = n-1;↵
int q; cin>>q;↵
REP(i,q) {↵
int v; cin>>v;↵
bool toblack = v>0;↵
v = abs(v);↵
int p = par[v];↵
if (toblack) {↵
--V;↵
int fr = ch[v] + (p != -1 && !black[p]);↵
E -= fr;↵
if (p != -1) {↵
--ch[p];↵
}↵
}else{↵
++V;↵
int fr = ch[v] + (p != -1 && !black[p]);↵
E += fr;↵
if (p != -1) {↵
++ch[p];↵
}↵
}↵
black[v] ^= 1;↵
cout<<V-E<<endl;↵
}↵
↵
}↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
5. [Rally 2014](https://szkopul.edu.pl/problemset/problem/BnzEADCfeJFjjev1Y9iHQANg/site/?key=statement) [By the way, I've been stuck on this one for super long. Currently getting wrong answer on one test case (89 pts) for unknown reason.] [UPD: I ACed this problem, but my solution is wrong. It's just very hard to block with a random generator. I'll try to think of & write a proper solution when I have some more time.]↵
↵
<spoiler summary="Current Spaghetti Code (with brute force checker and generator...)">↵
↵
```c↵
#include <bits/stdc++.h>↵
//#define int ll↵
//#undef BALBIT↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<int, int>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
//#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
//#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 5e5+5;↵
↵
// 1. Find longest chain↵
// 2. For each node, find minimum (chain position - max dist), and update all indeg↵
// 3. Do the same for the outdeg↵
// 3.1. Also update the case where there there's just a hanging thread↵
// 4. Use seg tree or smth to update ans↵
// 5. Check for longest chain not connected to original↵
// by the way this is wrong↵
vector<int> g[maxn], gt[maxn];↵
↵
int mxd[maxn], frm[maxn]; // for building original chain↵
bool onP[maxn]; // P is the biggest chain↵
int Pid[maxn];↵
vector<int> ord;↵
vector<int> P;↵
int indeg[maxn];↵
int n,m;↵
↵
int getlen(int ban){↵
REP(i,n) {↵
indeg[i] = SZ(gt[i]); mxd[i] = 0;↵
}↵
for( int u : g[ban]) {↵
--indeg[u];↵
}↵
queue<int> q;↵
REP(i,n) {↵
if (indeg[i] == 0 && i!=ban) q.push(i);↵
}↵
int bg = 0, bgv = -1;↵
while (!q.empty()) {↵
int v=q.front(); q.pop();↵
assert(v != ban);↵
if (mxd[v] == 0) {↵
mxd[v] = 1;↵
}↵
if (mxd[v] > bg) {↵
bg = mxd[v]; bgv = v;↵
}↵
for (int u : g[v]) {↵
if (u == ban) continue;↵
if (mxd[u] < mxd[v] + 1) {↵
mxd[u] = mxd[v] + 1;↵
}↵
if (--indeg[u] == 0) {↵
q.push(u);↵
}↵
}↵
}↵
// bug(ban, bg);↵
return bg;↵
}↵
↵
↵
↵
void buildP(){↵
// also build topo order↵
↵
REP(i,n) {↵
indeg[i] = SZ(gt[i]);↵
}↵
↵
queue<int> q;↵
REP(i,n) {↵
if (indeg[i] == 0) q.push(i);↵
}↵
int bg = 0, bgv = -1;↵
while (!q.empty()) {↵
int v=q.front(); q.pop(); ord.pb(v);↵
if (mxd[v] == 0) {↵
mxd[v] = 1; frm[v] = -1;↵
}↵
if (mxd[v] > bg) {↵
bg = mxd[v]; bgv = v;↵
}↵
for (int u : g[v]) {↵
if (mxd[u] < mxd[v] + 1) {↵
mxd[u] = mxd[v] + 1;↵
frm[u] = v;↵
}↵
if (--indeg[u] == 0) {↵
q.push(u);↵
}↵
}↵
}↵
assert(SZ(ord) == n);↵
for (; bgv != -1; bgv = frm[bgv]) {↵
P.pb(bgv); onP[bgv] = 1;↵
}↵
reverse(ALL(P));↵
REP(i, SZ(P)){↵
Pid[P[i]] = i;↵
bug(P[i], i);↵
}↵
}↵
↵
pair<int, int> dp[maxn];↵
↵
inline void MN(pii &a, pii b) {if (b.f < a.f || (b.f == a.f && b.s > a.s)) a = b;}↵
inline void MX(pii &a, pii b) {if (b.f > a.f || (b.f == a.f && b.s < a.s)) a = b;}↵
↵
vector<pair<int, bool> > yo[maxn];↵
↵
void upd(int l, int r, int v) {↵
if (l > r || l == -1) return;↵
bug(l,r,v);↵
yo[l].pb({v, 1});↵
yo[r+1].pb({v, 0});↵
}↵
↵
pair<bool, int> bad(int M){↵
int ctr = 0;↵
REP(i,SZ(P)) {↵
for (pii p : yo[i]) {↵
if (p.f <= M) {↵
ctr += p.s?1:-1;↵
}↵
}↵
if (ctr == 0) {↵
return {1, P[i]};↵
}↵
}↵
return {0, -1};↵
}↵
↵
void buildR(){↵
for (int it = SZ(ord)-1; it>=0; --it) {↵
int v = ord[it];↵
int prv = SZ(P)-1;↵
if (onP[v]) {↵
dp[v] = {Pid[v],Pid[v]};↵
}else{↵
dp[v] = {SZ(P)-1,SZ(P)};↵
for (int u : g[v]) {↵
MN(dp[v] , {dp[u].f-1, dp[u].s});↵
}↵
for (int u : g[v]) {↵
if (dp[u].s > dp[v].s) {↵
prv = min(prv, dp[u].f - 1);↵
}↵
}↵
}↵
int bg = -1;↵
// bug(v, dp[v].f, dp[v].s);↵
for(int u : gt[v]) {↵
if (onP[u]) {↵
upd(Pid[u]+1, dp[v].s-1, dp[v].f - Pid[u] - 1);↵
bg = max(bg, Pid[u]);↵
}↵
}↵
if (!onP[v]) {↵
if (v == 2) {↵
bug(dp[v].s, prv, bg);↵
}↵
upd(dp[v].s, dp[v].s, prv-bg-1);↵
}↵
upd(-1+1, dp[v].s-1, dp[v].f); // loose end↵
}↵
↵
REP(it, SZ(ord)) {↵
int v = ord[it];↵
int prv = 0;↵
pair<int, int> old = dp[v];↵
if (onP[v]) {↵
dp[v] = {Pid[v],Pid[v]};↵
}else{↵
dp[v] = {0, -1};↵
for (int u : gt[v]) {↵
MX(dp[v] , {dp[u].f+1, dp[u].s});↵
}↵
for (int u : gt[v]) {↵
if (dp[u].s < dp[v].s) {↵
prv = max(prv, dp[u].f+1);↵
}↵
}↵
}↵
int smo = SZ(P);↵
for(int u : g[v]) {↵
if (onP[u]) {↵
smo = min(smo, Pid[u]);↵
upd(dp[v].s+1, Pid[u]-1, Pid[u] - dp[v].f - 1);↵
}↵
}↵
if (!onP[v]) {↵
upd(dp[v].s+1, old.s-1, old.f-dp[v].f);↵
if (v == 1) {↵
bug(old.s, dp[v].s, old.f, dp[v].f);↵
}↵
// assert(dp[v].s <= old.s);↵
upd(dp[v].s, dp[v].s, smo-prv-1);↵
}↵
upd(dp[v].s+1, SZ(P)-1, SZ(P) - dp[v].f - 1); // loose end↵
}↵
}↵
↵
pii fast() {↵
↵
↵
buildP();↵
buildR();↵
↵
int l = -1, r = n;↵
while(l!=r) {↵
int mid = ((l+r)/2) - (((l+r)<0) && ((l+r)%2)); // floored division↵
if (bad(mid).f) {↵
l = mid+1;↵
}else{↵
r = mid;↵
}↵
}↵
bug(l);↵
return {bad(l-1).s+1,SZ(P) - (l+1)};↵
// cout<<<<endl;↵
}↵
↵
pii slow(){↵
int re = iinf;↵
int ri = -1;↵
REP(i,n) {↵
int yar = getlen(i)-1;↵
if (yar < re) {↵
re = yar; ri = i;↵
}↵
}↵
return {ri+1, re};↵
}↵
↵
signed main(){↵
IOS();↵
cin>>n>>m;↵
int yoi = 10000;↵
#ifndef BALBIT↵
yoi = 1;↵
#endif // BALBIT↵
REP(qqq, yoi) {↵
#ifdef BALBIT↵
REP(i,n+1) {↵
g[i].clear(); gt[i].clear();↵
yo[i].clear();↵
mxd[i]=frm[i]=onP[i]=Pid[i]=indeg[i]=0;↵
}↵
ord.clear(); P.clear();↵
#endif↵
↵
vector<pii> edges;↵
↵
vector<int> od(n); REP(i,n) od[i] = i;↵
random_shuffle(ALL(od));↵
set<pii> hv;↵
REP(i,m) {↵
int a,b;↵
#ifndef BALBIT↵
cin>>a>>b;↵
--a; --b;↵
#else↵
a = rand() % n; b = rand()%n; if (od[a] > od[b]) swap(a,b);↵
if (a == b || hv.count({a,b})) continue;↵
hv.insert({a,b});↵
edges.pb({a,b});↵
#endif↵
g[a].pb(b); gt[b].pb(a);↵
}↵
#ifdef BALBIT↵
pii A = fast();↵
pii B = slow();↵
bug(A.f, A.s, B.s);↵
if (A.s != B.s) {↵
bug(A.s, B.s);↵
for (pii p : edges) {↵
bug(p.f, p.s);↵
}↵
}↵
assert(A.s == B.s);↵
#else↵
pii A = fast();↵
↵
cout<<A.f<<' '<<getlen(A.f-1)-1<<endl;↵
#endif↵
}↵
↵
↵
↵
}↵
↵
/*↵
5 5↵
1 2↵
2 3↵
3 4↵
1 5↵
5 4↵
↵
9 7↵
1 2↵
2 3↵
3 4↵
6 7↵
7 8↵
8 9↵
9 5↵
↵
7 8↵
1 2↵
2 3↵
3 4↵
5 2↵
2 6↵
6 7↵
3 7↵
6 4↵
↵
5 5↵
1 3↵
3 4↵
2 5↵
3 5↵
2 3↵
*/↵
```↵
</spoiler>↵
↵
6. [Trips 2015](https://szkopul.edu.pl/problemset/problem/zKf5Ua8okcS0jngsrTgKVM9L/site/?key=statement) [Solved Jan 18]↵
↵
<spoiler summary="Fun-ness:">↵
3/10↵
↵
<spoiler summary="Comments">↵
I got stuck on Rally for too long and decided to try this one. ↵
↵
Thinking of the solution and implementing it was easy; getting it to pass on szkopul was not. ↵
↵
Not only are time limits different for each subtask, they also vary for each test case, meaning that you'll suffer a lot if you don't implement it in the same way the author did. ↵
↵
Also, I didn't see that there were multiple edges for a while. That was my bad.↵
</spoiler>↵
↵
<spoiler summary="Code (warning: dirty, with lots of breaks and debug stuff)">↵
↵
```c↵
#include <bits/stdc++.h>↵
#pragma GCC optimize("Ofast", "unroll-loops")↵
//#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 1e5+5;↵
↵
typedef array<ll, 121> Vec;↵
typedef array<Vec, 121> Mat;↵
↵
Mat M;↵
ll cap = (1ll<<61)-1;↵
↵
int LAY = 65;↵
Mat Mp[65];↵
↵
↵
inline ll prod(ll a, ll b) {↵
if (!b || !a) return 0;↵
if ((a) > (cap) / b + 1) return cap;↵
return min(a*b, cap);↵
}↵
↵
inline void add(ll &a, ll b) {↵
a = min(cap,a+b);↵
}↵
↵
int YO, END;↵
↵
void mul(Mat &c, Mat a, Mat b) {↵
REP(i,YO) REP(j,YO) if (i<j) swap(b[i][j], b[j][i]);↵
REP(i, YO) REP(j, YO) {↵
c[i][j] = 0;↵
REP(k,YO) {↵
add(c[i][j], prod(a[i][k], b[j][k]));↵
if (c[i][j] == cap) break;↵
}↵
}↵
}↵
↵
signed main(){↵
IOS();↵
int n,m; ll k; cin>>n>>m>>k;↵
↵
YO = n*3+1; END = YO-1;↵
↵
k += n;↵
↵
LAY = __lg(k+1)+2;↵
↵
REP(i,n) {↵
M[i*3][i*3+1] = 1;↵
M[i*3+1][i*3+2] = 1;↵
}↵
↵
REP(i,m) {↵
int a,b,c; cin>>a>>b>>c;↵
--a; --b;↵
M[a*3+2][b*3+3-c] += 1;↵
}↵
↵
Vec now; fill(ALL(now), 0);↵
REP(i,n) {↵
now[i*3+2] = 1;↵
M[i*3+2][END] = 1;↵
}↵
M[END][END] = 1;↵
↵
Mp[0] = M;↵
↵
ll psig = -1;↵
bool yoit = 0;↵
↵
REP1(i, LAY-1) {↵
bug(i);↵
mul(Mp[i], Mp[i-1], Mp[i-1]);↵
ll sg = 0;↵
REP(p,YO) {↵
if (p % 3 == 2)↵
add(sg, Mp[i][p][END]);↵
}↵
if (sg > k ) {↵
yoit = 1;↵
LAY = i+1; break;↵
}↵
psig = sg;↵
}↵
↵
ll re = 0;↵
↵
bool big = 0;ll sg= 0;↵
↵
for (int mi = LAY-1; mi>=0; --mi) {↵
Vec tmp;↵
fill(ALL(tmp), 0);↵
ll sig = 0;↵
REP(i, YO) {↵
tmp[i] = 0;↵
REP(j,YO) {↵
add(tmp[i], prod(now[j], Mp[mi][j][i]));↵
}↵
if (i == END) {↵
add(sig, tmp[i]);↵
}↵
}↵
bug(sig, k);↵
if (sig < k) {↵
sg = sig;↵
re += (1ll<<mi);↵
now = tmp;↵
}else big = 1;↵
}↵
↵
if (!big) {↵
assert(yoit != 1);↵
re = -1;↵
}↵
↵
cout<<re<<endl;↵
↵
↵
}↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Help">↵
Is there a fast way to find min(A*B, C) where A, B, and C can be 64-bit numbers?↵
I had to resort to doing ↵
↵
```c↵
inline ll prod(ll a, ll b) {↵
if (!b || !a) return 0;↵
if ((a) > (cap) / b + 1) return cap;↵
return min(a*b, cap);↵
}↵
```↵
↵
but it's obviously very slow. Also, szkopul doesn't support __int128.......↵
</spoiler>↵
↵
7. [Panini 2017](https://szkopul.edu.pl/problemset/problem/w-dbshXVyRol4LIT9jeP-bNn/site/?key=statement) [Solved Jan 19]↵
↵
<spoiler summary="Fun-ness">↵
↵
7/10↵
↵
<spoiler summary="Comments">↵
↵
This is a great problem! It feels awesome finding observations and separating this difficult-seeming problem into a few easy-to-handle cases. ↵
↵
One thing that surprised me was that I forgot an entire (fairly important) case that should've been easily caught with a random testcase but was still able to get 84 points, with only 2 subtasks showing WA. I guess this goes to show the importance of multitests, however annoying they are. ↵
↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 3e3+5;↵
↵
vector<pii> dp[maxn]; // {reaches to, cost}↵
ll smollest[maxn];↵
↵
signed main(){↵
IOS();↵
↵
int n,z,d; cin>>n>>z>>d;↵
↵
vector<ll> a(n+1);↵
vector<ll> sig(n+1);↵
↵
ll re = 0;↵
REP1(i,n) {↵
cin>>a[i];↵
if (a[i] < d) {↵
re += d-a[i]; a[i] = d;↵
}↵
if (i - z >= 0 && a[i] - a[i-z] < d) {↵
re += a[i-z] + d - a[i];↵
a[i] = a[i-z] + d;↵
}↵
bug(i, a[i]);↵
sig[i] = sig[i-1] + a[i];↵
}↵
a.pb(inf);↵
bug(re);↵
↵
dp[0].pb({0, 0});↵
↵
for (int i = 1; i<=n; ++i) {↵
ll cst = 0;↵
int ntook = 1;↵
int j = i;↵
ll base = inf;↵
for (; j>0 && ntook <= z && a[i]-a[j] <= d; --j, ++ntook) {↵
if (a[i] - a[j] == d) {↵
// try transition↵
if (dp[j][0].f <= a[j])↵
MN(base, dp[j][0].s + cst);↵
}↵
cst += a[i] - a[j];↵
}↵
↵
for (pii p : dp[j]) {↵
if (p.f <= a[i] - d) {↵
MN(base, p.s + cst);↵
}↵
}↵
↵
for (; j>0 && ntook <= z; --j, ++ntook) {↵
cst += a[i] - a[j];↵
MN(base, smollest[j-1] + cst);↵
}↵
↵
bug(i, base);↵
↵
int at = i;↵
↵
for (int rps = 0; ; ++rps) {↵
dp[at].pb({a[i] + rps * d, base});↵
ntook = 0;↵
for (; a[at] <= a[i] + (rps+1)*d && ntook <= z; ++at, ++ntook) {↵
if (ntook) {↵
base += (rps+1)*d + a[i] - a[at];↵
}↵
}↵
if (ntook == 1) break;↵
--at;↵
}↵
smollest[i] = inf;↵
for (pii p : dp[i]) {↵
MN(smollest[i], p.s);↵
}↵
sort(ALL(dp[i]), [&](pii x, pii y){return x.f!=y.f?x.f < y.f : x.s < y.s;});↵
}↵
↵
ll ret = inf;↵
↵
{↵
ret = smollest[n];↵
// for (pii p : dp[n]) MN(ret, p.s);↵
}↵
↵
cout<<ret + re<<endl;↵
↵
}↵
↵
↵
/*↵
5 5 101↵
2 100 300 400 500↵
*/↵
↵
↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
8. [Crossroads of Parity 2017](https://szkopul.edu.pl/problemset/problem/-7cqC3RrH4e-Ar7DWy4GKzLv/site/?key=statement) [Solved Jan 19]↵
↵
<spoiler summary="Fun-ness">↵
↵
7/10↵
↵
<spoiler summary="Comments (major spoilers)">↵
This was a pretty cute and nice problem! I found it pretty easy but still very nice. ↵
↵
Let $f(S)$ denote the answer after adding the set of non-MST edges $S$.↵
↵
Obviously, because of MST properties, for a non-MST edge $e$ not in $S$, $f(S \cup \{e\}) > f(S)$, but it took me a bit of time to realize (and prove) that $e_1 > e_2 \implies f(S \cup \{e_1\}) > f(S \cup \{e_2\})$, which made the problem very nice and easy. ↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
#undef BALBIT↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 5e5+5;↵
↵
struct edge{↵
int v, u, i;↵
};↵
↵
int bot[maxn]; // bottom node of each edge↵
int par[maxn]; // parent of node↵
int L[maxn],R[maxn];↵
int IT = 0;↵
vector<edge> g[maxn];↵
↵
void dfs(int v, int p) {↵
par[v] = p;↵
L[v] = R[v] = IT++;↵
for (edge e : g[v]) {↵
if (e.u != p) {↵
bot[e.i] = e.u;↵
dfs(e.u, v);↵
R[v] = R[e.u];↵
}↵
}↵
}↵
↵
vector<edge> E;↵
↵
int dpar[maxn];↵
int find(int x) {return x == dpar[x]?x : dpar[x] = find(dpar[x]);}↵
void mrg(int a, int b) {↵
a=find(a); b = find(b);↵
dpar[a] = b;↵
}↵
↵
int s[maxn];↵
int QU(int e) {↵
int re = 0;↵
for (++e; e>0; e-=e&-e) {↵
re ^= s[e];↵
}↵
return re;↵
}↵
↵
inline bool isanc(int a, int b) {↵
return L[a] <= L[b] && R[a] >= R[b];↵
}↵
↵
void MO(int e, int v) {↵
for (++e; e<maxn; e+=e&-e) {↵
s[e] ^= v;↵
}↵
}↵
↵
vector<edge> lft;↵
bool intree[maxn];↵
↵
int get(int id, ll k) { // k = 1 => find the cheapest↵
bug(id);↵
if (k > (1ll<<min(SZ(lft), 62ll))) {↵
return -1;↵
}↵
--k; // now change to binary rep↵
if (intree[id]) {↵
int bt = bot[id];↵
int re = QU(R[bt]) ^ QU(L[bt]-1);↵
REP(j, min(62ll, SZ(lft))) {↵
if (k & (1ll<<j)) {↵
re ^= isanc(bt, lft[j].u);↵
re ^= isanc(bt, lft[j].v);↵
}↵
}↵
return re;↵
}else{↵
REP(j, min(62ll, SZ(lft))) {↵
if (k & (1ll<<j)) {↵
if (lft[j].i == id) return 1;↵
}↵
}↵
return 0;↵
}↵
}↵
↵
signed main(){↵
IOS();↵
int n,m; cin>>n>>m;↵
REP(i,n) dpar[i] = i;↵
bool totpar = 0;↵
REP(i,m) {↵
int a,b; cin>>a>>b; --a; --b;↵
E.pb({a,b,i});↵
if (find(a) != find(b)) {↵
mrg(a,b);↵
g[a].pb(E.back());↵
g[b].pb({b,a,i});↵
intree[i] = 1;↵
}else {↵
lft.pb(E.back());↵
}↵
}↵
dfs(0, -1);↵
REP(i,n) {↵
int p; cin>>p;↵
MO(L[i], p); // don't forget L[i]!!!↵
}↵
↵
ll K; cin>>K;↵
↵
REP(i,m) {↵
cout<<get(i, K)<<' ';↵
}↵
↵
cout<<endl;↵
↵
int q; cin>>q;↵
while (q--) {↵
char c; cin>>c;↵
if (c == 'M') {↵
int v; cin>>v;↵
--v; MO(L[v], 1);↵
totpar ^= 1;↵
}else if (c == 'K') {↵
cin>>K;↵
}else{↵
int i; cin>>i; --i;↵
if (totpar == 1) cout<<-1<<endl;↵
else cout<<get(i,K)<<endl;↵
}↵
}↵
↵
↵
}↵
↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
9. [Hydrocontest 2016](https://szkopul.edu.pl/problemset/problem/y9HM1ctDU8V8xLMRUYACDIRs/site/?key=statement) [Solved Jan 30]↵
↵
<spoiler summary="Fun-ness">↵
↵
7/10↵
↵
<spoiler summary="Comments">↵
I enjoyed this one quite a lot. Analysis was clean and the implementation was, while difficult, not as hard as I initially thought (which was that the graph was a general cactus, with some edges on no cycles). ↵
↵
BTW, I was gone for the past week due to a participating in a camp that took quite a bit more time than I expected.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 5e5+5;↵
↵
// 1. Find all faces and label each face as a node↵
// 2. Choose a face as the root and dfs↵
// 3. After finding the answer for each node (win or lose or nothing) wrt to each face except for transition nodes, dfs again for each face and push answer down↵
// 4. Use the answers for each face wrt to each node, answer each node↵
↵
vector<int> g[maxn];↵
bool seen[maxn];↵
vector<vector<int> > face; // faces!↵
vector<vector<int> > type; // for each (face, point), find the node type here (-1 for lose, 1 for win, 0 for nothing)↵
↵
vector<int> touchface[maxn]; // faces touching this node↵
vector<int> faceval[maxn]; // values of faces touching this node,↵
↵
int par[maxn];↵
int ts[maxn]; int IT = 0;↵
↵
void dfs1(int v, int p) {↵
par[v] = p;↵
seen[v] = 1;↵
ts[v] = IT++;↵
for (int u : g[v]) {↵
if (u == p) continue; // no double edges guaranteed↵
if (seen[u]) {↵
if (ts[u] < ts[v]) {↵
// u is ancestor of v↵
vector<int> nf;↵
for (int at = v; at != u; at = par[at]) {↵
nf.pb(at);↵
}↵
nf.pb(u);↵
for (int x : nf) {↵
touchface[x].pb(SZ(face));↵
}↵
face.pb(nf);↵
type.pb({});↵
}↵
}else{↵
dfs1(u, v);↵
}↵
}↵
}↵
↵
void getans(int f, int w, int wval) { // get all the answers for face f, given that the dp for node w is wval↵
int m = SZ(face[f]);↵
vector<int> &T = type[f];↵
REP(i, m) {↵
if (T[i] == -5) {↵
T[i] = wval;↵
}↵
}↵
vector<int> ans(m); // answer for this node, facing this face↵
int nwin = 0;↵
REP(i,m) {↵
if (T[i] == 1) {↵
++nwin;↵
}↵
}↵
int lastwin = -10000000;↵
REP(i, 2*m) {↵
if (i >= m) {↵
if ((i-lastwin) < m && (i - lastwin) % 2 == 0) {↵
// win!↵
ans[i%m] = 1;↵
}↵
}↵
if (T[i%m] == 1) {↵
lastwin = i;↵
}↵
}↵
lastwin = 3*m;↵
for (int i = 2*m-1; i>=0; --i) {↵
if (i < m) {↵
if ((lastwin - i) < m && (lastwin-i)%2 == 0) {↵
ans[i] = 1;↵
}↵
}↵
if (T[i%m] == 1) lastwin = i;↵
}↵
REP(i,m) {↵
if (ans[i] == 0) {↵
if ((nwin == 0) || (nwin==1 && T[i] == 1)) {↵
// no other winning nodes left↵
ans[i] = m % 2 == 0? 2:3 ;↵
}else{↵
ans[i] = -1;↵
}↵
}↵
}↵
↵
REP(i,m) {↵
int v = face[f][i];↵
if (v == w) continue;↵
assert(SZ(touchface[v]) == SZ(faceval[v]));↵
int nwin = 0; int nflip = 0;↵
REP(j, SZ(touchface[v])) {↵
int f2 = touchface[v][j];↵
if (f2 == f) {↵
faceval[v][j] = ans[i];↵
}else{↵
assert(faceval[v][j] != -5);↵
}↵
if (faceval[v][j] == 1) ++nwin;↵
else if (faceval[v][j] == 3) ++nflip;↵
}↵
REP(j, SZ(touchface[v])) {↵
int f2 = touchface[v][j];↵
if (f2 == f) {↵
continue;↵
}↵
if (faceval[v][j] == 1) {↵
if (nwin == 1) {↵
getans(f2, v, nflip%2==1?1:2);↵
}else{↵
getans(f2, v, 1);↵
}↵
}else{↵
if (nwin) {↵
getans(f2, v, 1);↵
}else{↵
getans(f2, v, (nflip - (faceval[v][j] == 3))% 2 == 1? 1 : 2);↵
}↵
}↵
}↵
}↵
↵
}↵
↵
int dfs2(int f, int w) { // i'm at face F, working on point w. -1: losing node, 1: winning, 2: no flip node, 3: force flip node↵
int m = SZ(face[f]);↵
vector<int> &val = type[f];↵
val.resize(m,-5);↵
int wherew = -1;↵
REP(i, m) {↵
↵
int v = face[f][i];↵
// bug(f,i,w,v);↵
if (v == w) {↵
wherew = i; continue;↵
}↵
val[i] = 2;↵
vector<int> tmp;↵
for (int f2 : touchface[v]) {↵
if (f2 == f) {↵
faceval[v].pb(-5);↵
}else{↵
int gt = dfs2(f2, v);↵
faceval[v].pb(gt);↵
tmp.pb(gt);↵
}↵
}↵
for (int gt : tmp){↵
if (gt == -1 || gt == 2) continue; // no one will walk into a losing node, and no-flips do nothing↵
if (gt == 1) {↵
val[i] = 1; break; // everyone will walk a winning node!↵
}↵
if (gt == 3) {↵
val[i] ^= 1;↵
}↵
}↵
if (val[i] == 3) {↵
val[i] = 1; // winnin'↵
}↵
bug(f, i, v, val[i]);↵
}↵
↵
if (wherew == -1) {↵
// is the root↵
getans(f, -1, -1);↵
return -100;↵
}↵
↵
bool anywin = 0;↵
REP(i,m) {↵
if (val[i] == 1) {↵
anywin = 1; break;↵
}↵
}↵
↵
if (anywin == 0) {↵
return m % 2 == 0?2 : 3; // no flip or flip↵
}↵
REP1(i, m) {↵
↵
if (val[(i+wherew) % m] == 1 ) {↵
// encountered a winning node!↵
if (i % 2 == 0) {↵
return 1; // winning!↵
}↵
break;↵
}↵
}↵
↵
REP1(i, m) {↵
↵
if (val[(wherew-i+m) % m] == 1 ) {↵
// encountered a winning node!↵
if (i % 2 == 0) {↵
return 1; // winning!↵
}↵
break;↵
}↵
}↵
return -1; // there is a winning node, but the opponent will walk it↵
}↵
↵
↵
↵
signed main(){↵
IOS();↵
int n; cin>>n;↵
int m; cin>>m;↵
REP(i,m) {↵
int a,b;↵
cin>>a>>b; --a; --b;↵
g[a].pb(b); g[b].pb(a);↵
}↵
dfs1(0, -1);↵
REP(i,n) sort(ALL(touchface[i]));↵
↵
dfs2(0, -1);↵
↵
REP(i,n) {↵
bool haswin = 0;↵
int nflip = 0;↵
for (int s : faceval[i]) {↵
if (s == 1) haswin = 1;↵
else if (s == 3) {↵
++nflip;↵
}↵
}↵
if( haswin || nflip % 2 == 1) {↵
cout<<1<<endl;↵
}else{↵
cout<<2<<endl;↵
}↵
}↵
↵
↵
}↵
↵
/*↵
7 9↵
1 2↵
2 3↵
3 1↵
3 4↵
4 5↵
5 3↵
5 7↵
5 6↵
6 7↵
*/↵
↵
}↵
↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
10. [Sorcerers 2015](https://szkopul.edu.pl/problemset/problem/fuTBSUcQ2U9sVPYJUDI4JwIe/site/?key=statement)↵
11. [Direction Signs 2015](https://szkopul.edu.pl/problemset/problem/4roJ2TqCXhLN6ftK2jiWKlO9/site/?key=statement) [Solved Jan 20]↵
↵
<spoiler summary="Fun-ness">↵
↵
7/10↵
↵
<spoiler summary="Comments (major spoilers)">↵
I thought this was a nice problem, although not a very hard one (?) Maybe I've seen too many of these "The answer contains at least X% of the set" :P↵
↵
At first I wasn't sure if O(N^2 * M / 64) * 20 reps would pass, but with a couple of /2s it runs really comfortably in around 0.5s. ↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 1e5+5;↵
↵
int d[1005][202];↵
bitset<200> so[1005];↵
int R[1005];↵
↵
int from[1005], dp[1005];↵
↵
↵
signed main(){↵
IOS();↵
↵
mt19937 rnd(time(0));↵
↵
int n,m; cin>>n>>m;↵
--m;↵
REP(i,n) {↵
int r; cin>>r; R[i] = r;↵
REP(j,m) {↵
cin>>d[i][j]; d[i][j] -= r;↵
}↵
}↵
const int MAGIC = 20;↵
↵
int bst = 0;↵
vector<int>re;↵
↵
REP(qqq, MAGIC) {↵
int T = rnd()%n;↵
vector<int> same;↵
vector<pii> gv, lv;↵
REP(i,n) {↵
if (i == T) {↵
same.pb(i); continue;↵
}↵
int gr = 0;↵
int cnt = 0;↵
REP(j,m) {↵
so[i][j] = 0;↵
if (d[i][j] == d[T][j]) continue;↵
if (abs(d[i][j] - d[T][j]) >= 2) goto die;↵
↵
so[i][j] = 1; ++cnt;↵
if (d[i][j] > d[T][j]) {↵
if (gr == -1) goto die;↵
gr = 1;↵
}else{↵
if (gr == 1) goto die;↵
gr = -1;↵
}↵
}↵
↵
if (gr == 0) {↵
same.pb(i);↵
}else if (gr > 0) {↵
gv.pb({cnt,i});↵
}else{↵
lv.pb({cnt,i});↵
}↵
die:;↵
}↵
if (SZ(gv) + SZ(lv) + SZ(same) < bst) continue;↵
bug(T, bst, SZ(gv), SZ(lv), SZ(same));↵
sort(ALL(gv)); sort(ALL(lv));↵
↵
memset(from, -1, sizeof from);↵
↵
REP(i, SZ(gv)) {↵
int it = gv[i].s;↵
dp[it] = 1;↵
REP(j, i) {↵
if (dp[gv[j].s] + 1 > dp[it] && (so[it] | so[gv[j].s]) == so[it]) {↵
dp[it] = dp[gv[j].s] + 1;↵
from[it] = gv[j].s;↵
}↵
}↵
}↵
↵
↵
REP(i, SZ(lv)) {↵
int it = lv[i].s;↵
dp[it] = 1;↵
REP(j, i) {↵
if (dp[lv[j].s] + 1 > dp[it] && (so[it] | so[lv[j].s]) == so[it]) {↵
dp[it] = dp[lv[j].s] + 1;↵
from[it] = lv[j].s;↵
}↵
}↵
}↵
↵
int btog = 0;↵
int bg = -1, bl = -1;↵
for (pii G : gv) {↵
if (dp[G.s] > btog) {↵
btog = dp[G.s]; bg = G.s; bl = -1;↵
}↵
}↵
for (pii L : lv) {↵
if (dp[L.s] > btog) {↵
btog = dp[L.s]; bl = L.s; bg = -1;↵
}↵
}↵
for (pii G : gv) for (pii L : lv) {↵
if (dp[G.s] + dp[L.s] > btog && ((so[G.s] & so[L.s]).count() == 0)) {↵
btog = dp[G.s] + dp[L.s];↵
bg = G.s; bl = L.s;↵
}↵
}↵
↵
if (btog + SZ(same) > bst) {↵
vector<pair<pii, int> > rat;↵
int stp = 100000;↵
for (int at = bg; at != -1; at = from[at]) {↵
rat.pb({{R[at], stp}, at});↵
--stp;↵
}↵
stp = -100000;↵
for (int at = bl; at != -1; at = from[at]) {↵
rat.pb({{R[at], stp},at});↵
++stp;↵
}↵
↵
for (int t : same) {↵
rat.pb({{R[t], 0},t});↵
}↵
↵
sort(ALL(rat)); reverse(ALL(rat));↵
↵
assert(SZ(rat) == btog + SZ(same));↵
↵
bst = SZ(rat); re.clear();↵
↵
for (auto e : rat) {↵
re.pb(e.s+1);↵
}↵
}↵
↵
}↵
↵
cout<<SZ(re)<<endl;↵
↵
for (int x : re) cout<<x<<' ';↵
cout<<endl;↵
↵
}↵
↵
↵
/*↵
4 4↵
3 3 3 4↵
3 4 4 4↵
3 3 4 4↵
4 4 4 4↵
*/↵
↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
Note: I'll also leave comments/hints here in case I manage to solve them or (unfortunately) have to dig around CSDN for their solutions :)
↵
It seems to me that POI is better suited for this format as their editorials are quite difficult to find (if possible [at all](https://szkopul.edu.pl/problemset/problem/v2Y2_UW56ENMcbwP22tkTb7a/site/?key=statement)). ↵
↵
While Ivan's original challenge was supposed to last an entire year, I'm not nearly as patient, so I won't look for editorials only until February 1st (in just over 2 weeks). Hopefully I'll have completed at least 80% by that time. Until then, GLHF!!!↵
↵
The List:↵
↵
1. [Multidrink 2013](https://szkopul.edu.pl/problemset/problem/GyDCbdIgFY5FsMa9iIsBl3hf/site/?key=statement) [Solved Jan 15]↵
↵
<spoiler summary="Fun-ness:">↵
5/10↵
↵
<spoiler summary="Comments">↵
My thought process on this problem went like "ew this is disgusting implementation" => "oh actually it's not so bad" => "oh no it's actually disgusting implementation"↵
↵
But I actually enjoyed this one more than most heavy casework/implementation problems because, while you have to be very careful about the dp transitions and especially their order, it's not too hard to prove once you have it written out. ↵
↵
<spoiler summary="my ugly code (if ppl not doing the challenge want to take a peek?)">↵
↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"BRAK\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 1e6+5;↵
↵
vector<int> pth; // path from s to t!↵
↵
int dp1[maxn], dp2[maxn]; // maximum number of free steps after {1: stomping here, 2: being here but not stomping}↵
vector<pii> run1[maxn], run2[maxn]; // for restoring answer↵
bool onpth[maxn];↵
↵
vector<pii> g[maxn]; // {to, edge id}↵
↵
bool findpth(int v, int T, int p) {↵
if (v == T) {↵
pth.pb(T); return 1;↵
}↵
for (pii u : g[v]) {↵
if (u.f != p && findpth(u.f,T,v)) {↵
pth.pb(v); onpth[u.s] = 1; return 1;↵
}↵
}↵
return 0;↵
}↵
↵
#define piii pair<pii,int>↵
↵
void dfs(int v, int par) {↵
dp2[v] = 3; // i'm so free i haven't even stomped yet↵
dp1[v] = 2; // yarrr i'm freshly stomped mmm↵
run1[v].pb({v, -1});↵
vector<piii > us;↵
for (pii p : g[v]) {↵
int u = p.f;↵
if (!onpth[p.s] && p.f != par) {↵
// tree edge!↵
dfs(u,v);↵
us.pb({{dp1[u],dp2[u]}, u});↵
}↵
}↵
↵
sort(ALL(us), [&](piii a, piii b) {↵
if (a.f.f == 2 || b.f.f == 2) return a.f.f > b.f.f; // i want to work with walking the leaf nodes first↵
if (a.f.f != b.f.f) return a.f.f > b.f.f;↵
if (a.f.f == 1) {↵
return a.f.s < b.f.s; // waste a bad dp↵
}↵
return a.f.s < b.f.s; // doesn't matter at this point ig↵
} );↵
for (auto rr : us) {↵
int u = rr.s;↵
↵
if (dp2[v] == 3){ // work with node free, this time we haven't stomped yet↵
if (dp1[u] == 2) {↵
// it's a leaf or something, anyways we can ignore it after stomping and come back↵
run2[v].pb({u,1});↵
goto dp2done;↵
}else{↵
if (dp1[u]==1) { // i stomp it and come back?↵
run2[v].pb({u,1});↵
run2[v].pb({v,-1});↵
dp2[v] = 2;↵
goto dp2done;↵
}else { // all hopeless, i have to stomp myself first↵
run2[v].pb({v,-1});↵
dp2[v] = 2;↵
}↵
}↵
}↵
if (dp2[v] == 2) {↵
// im forced to have stomped here now↵
// this will be equivalent to a later one↵
if (dp2[u] == 2) {↵
run2[v].pb({u,2});↵
dp2[v] = 1;↵
goto dp2done;↵
}else{↵
dp2[v] = 0;↵
goto dp2done;↵
}↵
}↵
if (dp2[v] == 1) {↵
if (dp1[u] == 2) {↵
run2[v].pb({u,1});↵
dp2[v] = 1;↵
goto dp2done;↵
}else{↵
dp2[v] = 0;↵
goto dp2done;↵
}↵
}↵
dp2done:;↵
}↵
sort(ALL(us), [&](piii a, piii b) {↵
return a.f.f < b.f.f; // you want to waste a bad dp1 early on↵
} );↵
for (auto rr : us) {↵
int u = rr.s;↵
↵
if (dp1[v] == 2) {↵
if (dp2[u] == 2) {↵
run1[v].pb({u,2});↵
dp1[v] = 1;↵
goto dp1done;↵
}else{↵
dp1[v] = 0;↵
goto dp1done;↵
}↵
}↵
↵
if (dp1[v] == 1) {↵
if (dp1[u] == 2) {↵
run1[v].pb({u,1});↵
dp1[v] = 1;↵
goto dp1done;↵
}else{↵
dp1[v] = 0;↵
goto dp1done;↵
}↵
}↵
↵
dp1done:;↵
↵
}↵
if (dp2[v] == 3) {↵
run2[v].pb({v, -1});↵
dp2[v] = 2;↵
} // no point in being super free now, 2 is good enough↵
assert(dp2[v] >= dp1[v]);↵
}↵
↵
vector<int> re;↵
↵
void prt(int v, int tp) {↵
if (tp == -1) {↵
re.pb(v); return;↵
}↵
for (pii p : tp==1?run1[v]:run2[v]) {↵
prt(p.f, p.s);↵
}↵
}↵
↵
signed main(){↵
IOS();↵
int n; cin>>n;↵
REP(i,n-1) {↵
int a,b; cin>>a>>b;↵
g[a].pb({b,i});↵
g[b].pb({a,i});↵
}↵
↵
findpth(1, n, -1);↵
reverse(ALL(pth));↵
↵
for (int x : pth) bug(x);↵
↵
int can = 1;↵
↵
vector<int> tp(SZ(pth));↵
↵
↵
REP(i, SZ(pth)) {↵
tp[i] = can;↵
int v = pth[i];↵
dfs(v, -1);↵
bug(v, can);↵
if (can == 0) GG();↵
if (i == SZ(pth)-1 && can == 1 && dp1[v] != 2) GG(); // can't stomp the last one first↵
bug(v, dp1[v], dp2[v]);↵
if (can == 2) {↵
can = dp2[v];↵
}else{↵
can = dp1[v];↵
}↵
}↵
bug(can);↵
if (can == 0 || can == 1) GG();↵
↵
REP(i, SZ(pth)) {↵
prt(pth[i], tp[i]);↵
}↵
↵
for (int x : re) cout<<x<<endl;↵
↵
}↵
↵
```↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
2. [Snake 2014](https://szkopul.edu.pl/problemset/problem/3zwfwt3ZGc2f6NndNgzS3Dfu/site/?key=statement)↵
3. [Arkanoid 2016](https://szkopul.edu.pl/problemset/problem/O730xgZEVynTWBmscBinhMbD/site/?key=statement) [Solved Jan 16]↵
↵
<spoiler summary="Fun-ness:">↵
4/10↵
↵
<spoiler summary="Comments">↵
↵
Another heavy implementation problem. Actually, the implementation isn't terrible (if you split the grid into 2N x 2M nodes), but I spent a long time debugging because I didn't realize that most exGCD implementations can't handle negative numbers well...↵
↵
<spoiler summary="more ugly code">↵
↵
```c↵
#include <bits/stdc++.h>↵
//#undef BALBIT↵
using namespace std;↵
#define ll long long↵
#define int ll↵
#define pii pair<int, int>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b) % mo;↵
}↵
↵
const int maxn = 1e5+5;↵
↵
int n,m,npts;↵
↵
pii flip(pii pt, pii dir) {↵
if (dir.f == -1 && pt.f) {↵
pt.f = 4*m-pt.f;↵
}↵
if (dir.s == -1 && pt.s) {↵
pt.s = 4*n-pt.s;↵
}↵
return pt;↵
}↵
↵
struct point{↵
↵
};↵
↵
vector<pair<pii, pii> > from[maxn]; // x=1 or 3, a-value↵
↵
↵
ll euclid(ll a, ll b, ll &x, ll &y) {↵
if (b) { ll d = euclid(b, a % b, y, x);↵
return y -= a/b * x, d; }↵
return x = 1, y = 0, a;↵
}↵
↵
↵
pii get(pii p) {↵
int piff = p.f - p.s; bug(piff);↵
int x = 0;↵
↵
if ((piff-1) % 4 == 0) x = 1;↵
else x = 3;↵
↵
pii k;↵
euclid(-m,n,k.f,k.s);↵
if (k.f * -m + k.s * n < 0) {↵
k.f *= -1; k.s *= -1;↵
}↵
↵
int RHS = (piff - x) / 4; assert((piff-x)%4==0);↵
↵
k.f *= RHS; k.s *= RHS;↵
↵
ll a = p.s + k.s * 4 * n; a %= (4*n*m);↵
if (a < 0) a += 4*n*m;↵
↵
bug(p.f, p.s, x, a);↵
return {x, a};↵
}↵
↵
ll smat(vector<pii> var){↵
array<set<pair<pii, pii> >, 4> s; // for the two values of x shift↵
↵
REP(i,npts) {↵
int x,y; tie(x,y) = var[i]; x*=2; y*=2; --x; --y;↵
↵
vector<pii> v;↵
vector<pii> vf;↵
if (x-1!=0){↵
// left edge↵
v.pb(flip({x-1,y}, {1,-1}));↵
v.pb(flip({x-1,y}, {1,+1}));↵
↵
vf.pb(flip({x-1,y}, {-1,-1}));↵
vf.pb(flip({x-1,y}, {-1,+1}));↵
}↵
if (x+1!=m*2){↵
// right edge↵
v.pb(flip({x+1,y}, {-1,-1}));↵
v.pb(flip({x+1,y}, {-1,+1}));↵
↵
vf.pb(flip({x+1,y}, {1,-1}));↵
vf.pb(flip({x+1,y}, {1,+1}));↵
}↵
if (y+1!=n*2){↵
// top edge↵
v.pb(flip({x,y+1}, {1,-1}));↵
v.pb(flip({x,y+1}, {-1,-1}));↵
↵
vf.pb(flip({x,y+1}, {1,1}));↵
vf.pb(flip({x,y+1}, {-1,1}));↵
}↵
if (y-1!=0){↵
// bottom edge↵
v.pb(flip({x,y-1}, { 1,+1}));↵
v.pb(flip({x,y-1}, {-1,+1}));↵
↵
vf.pb(flip({x,y-1}, { 1,-1}));↵
vf.pb(flip({x,y-1}, {-1,-1}));↵
}↵
↵
REP(j, SZ(v)) {↵
pii p = v[j];↵
pii pa = get(p);↵
int x = pa.f, a = pa.s;↵
↵
pii fop = get(vf[j]);↵
↵
from[i].pb({{a, x}, fop});↵
s[x].insert({{a, i}, fop});↵
}↵
↵
}↵
↵
pii nowdir = {-1,1};↵
pii nowpt = flip({m,0}, nowdir);↵
pii A = get(nowpt);↵
↵
bug(A.f, A.s);↵
↵
pii tmp = get(flip({m-1,1}, nowdir));↵
bug(tmp.f, tmp.s);↵
↵
ll ret = 0;↵
↵
while (SZ(s[1])) {↵
auto nxt = s[A.f].lower_bound({{A.s, -1},{-1,-1}});↵
if (nxt == s[A.f].end()) nxt = s[A.f].begin();↵
ll df = (*nxt).f.f - A.s;↵
assert(df != 0);↵
↵
if (df < 0) df += 4*n*m; // not sure, maybe 2nm??↵
ret += df;↵
↵
bug(df, ret);↵
↵
A = (*nxt).s;↵
// A = get(nowpt);↵
↵
int bye = (*nxt).f.s;↵
bug(bye);↵
for (auto p : from[bye]) {↵
int X = p.f.s;↵
p.f.s = bye;↵
s[X].erase(p);↵
}↵
}↵
↵
return ret;↵
}↵
↵
int yo[500][500];↵
↵
ll dumb(vector<pii> var) {↵
int i =0;↵
for (pii p : var) {↵
int x = p.f, y = p.s; x = x*2-1; y = y*2-1;↵
yo[x+1][y]++;↵
yo[x][y+1]++;↵
yo[x-1][y]++;↵
yo[x][y-1]++;↵
yo[x][y]=1;↵
++i;↵
}↵
int x = m, y = 0;↵
int dx = -1, dy = 1;↵
int bar = 0;↵
int re = 0;↵
while (bar < npts) {↵
x += dx; y += dy; ++re;↵
↵
pii tmp = get(flip({x,y}, {dx, dy}));↵
↵
bug(x,y,re,tmp.f, tmp.s);↵
if (yo[x][y]) {↵
// bump!↵
REP(ss, 4){↵
int tx = (ss-1)%2; // -1 0 1 0↵
int ty = (2-ss)%2; // 0 1 0 -1↵
if (yo[tx+x][ty+y]) {↵
int X = tx+x, Y = ty+y;↵
↵
if (tx) dx *= -1;↵
else dy *= -1;↵
↵
for (int sx:{-1,1}) for (int sy:{-1,1}) {↵
--yo[X+sx][Y+sy];↵
}↵
yo[X][Y] = 0;↵
goto yar;↵
}↵
}↵
↵
yar:;↵
↵
++bar;↵
}else{↵
if (x == 0 || x == 2*m) dx *= -1;↵
if (y == 0 || y == 2*n) dy *= -1;↵
}↵
}↵
return re;↵
}↵
↵
signed main(){↵
IOS();↵
cin>>m>>n>>npts; // m is for X, n is for Y↵
↵
vector<pii> var;↵
REP(i,npts) {↵
int x,y; cin>>x>>y; var.pb({x,y});↵
}↵
↵
cout<< smat(var)<<endl;↵
↵
// ll poo = dumb(var);↵
↵
// bug(ss, poo);↵
↵
}↵
```↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
↵
↵
4. [Strikes 2017](https://szkopul.edu.pl/problemset/problem/lR_LabSUC2n7EMmDHpw-wk_b/site/?key=statement) [Solved Jan 16]↵
↵
<spoiler summary="Oops">↵
Oops, I accidentally slipped a trivial one in this list X_X↵
↵
I thought it was ~80 solves in the first round but it turned out to be ~80 solves in the second round haha↵
↵
I'll add direction signs to the list to compensate for this one↵
↵
<spoiler summary="code :/">↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 5e5+5;↵
↵
vector<int> g[maxn];↵
int par[maxn];↵
int ch[maxn]; // number of white children↵
bool black[maxn];↵
↵
void dfs(int v, int p) {↵
par[v] = p;↵
for (int u : g[v]) {↵
if (u != p) {↵
dfs(u,v);↵
++ch[v];↵
}↵
}↵
}↵
↵
signed main(){↵
IOS();↵
↵
int n; cin>>n;↵
REP(i,n-1) {↵
int a,b; cin>>a>>b;↵
g[a].pb(b); g[b].pb(a);↵
}↵
dfs(1,-1);↵
↵
int V = n; int E = n-1;↵
int q; cin>>q;↵
REP(i,q) {↵
int v; cin>>v;↵
bool toblack = v>0;↵
v = abs(v);↵
int p = par[v];↵
if (toblack) {↵
--V;↵
int fr = ch[v] + (p != -1 && !black[p]);↵
E -= fr;↵
if (p != -1) {↵
--ch[p];↵
}↵
}else{↵
++V;↵
int fr = ch[v] + (p != -1 && !black[p]);↵
E += fr;↵
if (p != -1) {↵
++ch[p];↵
}↵
}↵
black[v] ^= 1;↵
cout<<V-E<<endl;↵
}↵
↵
}↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
5. [Rally 2014](https://szkopul.edu.pl/problemset/problem/BnzEADCfeJFjjev1Y9iHQANg/site/?key=statement) [By the way, I've been stuck on this one for super long. Currently getting wrong answer on one test case (89 pts) for unknown reason.] [UPD: I ACed this problem, but my solution is wrong. It's just very hard to block with a random generator. I'll try to think of & write a proper solution when I have some more time.]↵
↵
<spoiler summary="Current Spaghetti Code (with brute force checker and generator...)">↵
↵
```c↵
#include <bits/stdc++.h>↵
//#define int ll↵
//#undef BALBIT↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<int, int>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
//#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
//#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 5e5+5;↵
↵
// 1. Find longest chain↵
// 2. For each node, find minimum (chain position - max dist), and update all indeg↵
// 3. Do the same for the outdeg↵
// 3.1. Also update the case where there there's just a hanging thread↵
// 4. Use seg tree or smth to update ans↵
// 5. Check for longest chain not connected to original↵
// by the way this is wrong↵
vector<int> g[maxn], gt[maxn];↵
↵
int mxd[maxn], frm[maxn]; // for building original chain↵
bool onP[maxn]; // P is the biggest chain↵
int Pid[maxn];↵
vector<int> ord;↵
vector<int> P;↵
int indeg[maxn];↵
int n,m;↵
↵
int getlen(int ban){↵
REP(i,n) {↵
indeg[i] = SZ(gt[i]); mxd[i] = 0;↵
}↵
for( int u : g[ban]) {↵
--indeg[u];↵
}↵
queue<int> q;↵
REP(i,n) {↵
if (indeg[i] == 0 && i!=ban) q.push(i);↵
}↵
int bg = 0, bgv = -1;↵
while (!q.empty()) {↵
int v=q.front(); q.pop();↵
assert(v != ban);↵
if (mxd[v] == 0) {↵
mxd[v] = 1;↵
}↵
if (mxd[v] > bg) {↵
bg = mxd[v]; bgv = v;↵
}↵
for (int u : g[v]) {↵
if (u == ban) continue;↵
if (mxd[u] < mxd[v] + 1) {↵
mxd[u] = mxd[v] + 1;↵
}↵
if (--indeg[u] == 0) {↵
q.push(u);↵
}↵
}↵
}↵
// bug(ban, bg);↵
return bg;↵
}↵
↵
↵
↵
void buildP(){↵
// also build topo order↵
↵
REP(i,n) {↵
indeg[i] = SZ(gt[i]);↵
}↵
↵
queue<int> q;↵
REP(i,n) {↵
if (indeg[i] == 0) q.push(i);↵
}↵
int bg = 0, bgv = -1;↵
while (!q.empty()) {↵
int v=q.front(); q.pop(); ord.pb(v);↵
if (mxd[v] == 0) {↵
mxd[v] = 1; frm[v] = -1;↵
}↵
if (mxd[v] > bg) {↵
bg = mxd[v]; bgv = v;↵
}↵
for (int u : g[v]) {↵
if (mxd[u] < mxd[v] + 1) {↵
mxd[u] = mxd[v] + 1;↵
frm[u] = v;↵
}↵
if (--indeg[u] == 0) {↵
q.push(u);↵
}↵
}↵
}↵
assert(SZ(ord) == n);↵
for (; bgv != -1; bgv = frm[bgv]) {↵
P.pb(bgv); onP[bgv] = 1;↵
}↵
reverse(ALL(P));↵
REP(i, SZ(P)){↵
Pid[P[i]] = i;↵
bug(P[i], i);↵
}↵
}↵
↵
pair<int, int> dp[maxn];↵
↵
inline void MN(pii &a, pii b) {if (b.f < a.f || (b.f == a.f && b.s > a.s)) a = b;}↵
inline void MX(pii &a, pii b) {if (b.f > a.f || (b.f == a.f && b.s < a.s)) a = b;}↵
↵
vector<pair<int, bool> > yo[maxn];↵
↵
void upd(int l, int r, int v) {↵
if (l > r || l == -1) return;↵
bug(l,r,v);↵
yo[l].pb({v, 1});↵
yo[r+1].pb({v, 0});↵
}↵
↵
pair<bool, int> bad(int M){↵
int ctr = 0;↵
REP(i,SZ(P)) {↵
for (pii p : yo[i]) {↵
if (p.f <= M) {↵
ctr += p.s?1:-1;↵
}↵
}↵
if (ctr == 0) {↵
return {1, P[i]};↵
}↵
}↵
return {0, -1};↵
}↵
↵
void buildR(){↵
for (int it = SZ(ord)-1; it>=0; --it) {↵
int v = ord[it];↵
int prv = SZ(P)-1;↵
if (onP[v]) {↵
dp[v] = {Pid[v],Pid[v]};↵
}else{↵
dp[v] = {SZ(P)-1,SZ(P)};↵
for (int u : g[v]) {↵
MN(dp[v] , {dp[u].f-1, dp[u].s});↵
}↵
for (int u : g[v]) {↵
if (dp[u].s > dp[v].s) {↵
prv = min(prv, dp[u].f - 1);↵
}↵
}↵
}↵
int bg = -1;↵
// bug(v, dp[v].f, dp[v].s);↵
for(int u : gt[v]) {↵
if (onP[u]) {↵
upd(Pid[u]+1, dp[v].s-1, dp[v].f - Pid[u] - 1);↵
bg = max(bg, Pid[u]);↵
}↵
}↵
if (!onP[v]) {↵
if (v == 2) {↵
bug(dp[v].s, prv, bg);↵
}↵
upd(dp[v].s, dp[v].s, prv-bg-1);↵
}↵
upd(-1+1, dp[v].s-1, dp[v].f); // loose end↵
}↵
↵
REP(it, SZ(ord)) {↵
int v = ord[it];↵
int prv = 0;↵
pair<int, int> old = dp[v];↵
if (onP[v]) {↵
dp[v] = {Pid[v],Pid[v]};↵
}else{↵
dp[v] = {0, -1};↵
for (int u : gt[v]) {↵
MX(dp[v] , {dp[u].f+1, dp[u].s});↵
}↵
for (int u : gt[v]) {↵
if (dp[u].s < dp[v].s) {↵
prv = max(prv, dp[u].f+1);↵
}↵
}↵
}↵
int smo = SZ(P);↵
for(int u : g[v]) {↵
if (onP[u]) {↵
smo = min(smo, Pid[u]);↵
upd(dp[v].s+1, Pid[u]-1, Pid[u] - dp[v].f - 1);↵
}↵
}↵
if (!onP[v]) {↵
upd(dp[v].s+1, old.s-1, old.f-dp[v].f);↵
if (v == 1) {↵
bug(old.s, dp[v].s, old.f, dp[v].f);↵
}↵
// assert(dp[v].s <= old.s);↵
upd(dp[v].s, dp[v].s, smo-prv-1);↵
}↵
upd(dp[v].s+1, SZ(P)-1, SZ(P) - dp[v].f - 1); // loose end↵
}↵
}↵
↵
pii fast() {↵
↵
↵
buildP();↵
buildR();↵
↵
int l = -1, r = n;↵
while(l!=r) {↵
int mid = ((l+r)/2) - (((l+r)<0) && ((l+r)%2)); // floored division↵
if (bad(mid).f) {↵
l = mid+1;↵
}else{↵
r = mid;↵
}↵
}↵
bug(l);↵
return {bad(l-1).s+1,SZ(P) - (l+1)};↵
// cout<<<<endl;↵
}↵
↵
pii slow(){↵
int re = iinf;↵
int ri = -1;↵
REP(i,n) {↵
int yar = getlen(i)-1;↵
if (yar < re) {↵
re = yar; ri = i;↵
}↵
}↵
return {ri+1, re};↵
}↵
↵
signed main(){↵
IOS();↵
cin>>n>>m;↵
int yoi = 10000;↵
#ifndef BALBIT↵
yoi = 1;↵
#endif // BALBIT↵
REP(qqq, yoi) {↵
#ifdef BALBIT↵
REP(i,n+1) {↵
g[i].clear(); gt[i].clear();↵
yo[i].clear();↵
mxd[i]=frm[i]=onP[i]=Pid[i]=indeg[i]=0;↵
}↵
ord.clear(); P.clear();↵
#endif↵
↵
vector<pii> edges;↵
↵
vector<int> od(n); REP(i,n) od[i] = i;↵
random_shuffle(ALL(od));↵
set<pii> hv;↵
REP(i,m) {↵
int a,b;↵
#ifndef BALBIT↵
cin>>a>>b;↵
--a; --b;↵
#else↵
a = rand() % n; b = rand()%n; if (od[a] > od[b]) swap(a,b);↵
if (a == b || hv.count({a,b})) continue;↵
hv.insert({a,b});↵
edges.pb({a,b});↵
#endif↵
g[a].pb(b); gt[b].pb(a);↵
}↵
#ifdef BALBIT↵
pii A = fast();↵
pii B = slow();↵
bug(A.f, A.s, B.s);↵
if (A.s != B.s) {↵
bug(A.s, B.s);↵
for (pii p : edges) {↵
bug(p.f, p.s);↵
}↵
}↵
assert(A.s == B.s);↵
#else↵
pii A = fast();↵
↵
cout<<A.f<<' '<<getlen(A.f-1)-1<<endl;↵
#endif↵
}↵
↵
↵
↵
}↵
↵
/*↵
5 5↵
1 2↵
2 3↵
3 4↵
1 5↵
5 4↵
↵
9 7↵
1 2↵
2 3↵
3 4↵
6 7↵
7 8↵
8 9↵
9 5↵
↵
7 8↵
1 2↵
2 3↵
3 4↵
5 2↵
2 6↵
6 7↵
3 7↵
6 4↵
↵
5 5↵
1 3↵
3 4↵
2 5↵
3 5↵
2 3↵
*/↵
```↵
</spoiler>↵
↵
6. [Trips 2015](https://szkopul.edu.pl/problemset/problem/zKf5Ua8okcS0jngsrTgKVM9L/site/?key=statement) [Solved Jan 18]↵
↵
<spoiler summary="Fun-ness:">↵
3/10↵
↵
<spoiler summary="Comments">↵
I got stuck on Rally for too long and decided to try this one. ↵
↵
Thinking of the solution and implementing it was easy; getting it to pass on szkopul was not. ↵
↵
Not only are time limits different for each subtask, they also vary for each test case, meaning that you'll suffer a lot if you don't implement it in the same way the author did. ↵
↵
Also, I didn't see that there were multiple edges for a while. That was my bad.↵
</spoiler>↵
↵
<spoiler summary="Code (warning: dirty, with lots of breaks and debug stuff)">↵
↵
```c↵
#include <bits/stdc++.h>↵
#pragma GCC optimize("Ofast", "unroll-loops")↵
//#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 1e5+5;↵
↵
typedef array<ll, 121> Vec;↵
typedef array<Vec, 121> Mat;↵
↵
Mat M;↵
ll cap = (1ll<<61)-1;↵
↵
int LAY = 65;↵
Mat Mp[65];↵
↵
↵
inline ll prod(ll a, ll b) {↵
if (!b || !a) return 0;↵
if ((a) > (cap) / b + 1) return cap;↵
return min(a*b, cap);↵
}↵
↵
inline void add(ll &a, ll b) {↵
a = min(cap,a+b);↵
}↵
↵
int YO, END;↵
↵
void mul(Mat &c, Mat a, Mat b) {↵
REP(i,YO) REP(j,YO) if (i<j) swap(b[i][j], b[j][i]);↵
REP(i, YO) REP(j, YO) {↵
c[i][j] = 0;↵
REP(k,YO) {↵
add(c[i][j], prod(a[i][k], b[j][k]));↵
if (c[i][j] == cap) break;↵
}↵
}↵
}↵
↵
signed main(){↵
IOS();↵
int n,m; ll k; cin>>n>>m>>k;↵
↵
YO = n*3+1; END = YO-1;↵
↵
k += n;↵
↵
LAY = __lg(k+1)+2;↵
↵
REP(i,n) {↵
M[i*3][i*3+1] = 1;↵
M[i*3+1][i*3+2] = 1;↵
}↵
↵
REP(i,m) {↵
int a,b,c; cin>>a>>b>>c;↵
--a; --b;↵
M[a*3+2][b*3+3-c] += 1;↵
}↵
↵
Vec now; fill(ALL(now), 0);↵
REP(i,n) {↵
now[i*3+2] = 1;↵
M[i*3+2][END] = 1;↵
}↵
M[END][END] = 1;↵
↵
Mp[0] = M;↵
↵
ll psig = -1;↵
bool yoit = 0;↵
↵
REP1(i, LAY-1) {↵
bug(i);↵
mul(Mp[i], Mp[i-1], Mp[i-1]);↵
ll sg = 0;↵
REP(p,YO) {↵
if (p % 3 == 2)↵
add(sg, Mp[i][p][END]);↵
}↵
if (sg > k ) {↵
yoit = 1;↵
LAY = i+1; break;↵
}↵
psig = sg;↵
}↵
↵
ll re = 0;↵
↵
bool big = 0;ll sg= 0;↵
↵
for (int mi = LAY-1; mi>=0; --mi) {↵
Vec tmp;↵
fill(ALL(tmp), 0);↵
ll sig = 0;↵
REP(i, YO) {↵
tmp[i] = 0;↵
REP(j,YO) {↵
add(tmp[i], prod(now[j], Mp[mi][j][i]));↵
}↵
if (i == END) {↵
add(sig, tmp[i]);↵
}↵
}↵
bug(sig, k);↵
if (sig < k) {↵
sg = sig;↵
re += (1ll<<mi);↵
now = tmp;↵
}else big = 1;↵
}↵
↵
if (!big) {↵
assert(yoit != 1);↵
re = -1;↵
}↵
↵
cout<<re<<endl;↵
↵
↵
}↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Help">↵
Is there a fast way to find min(A*B, C) where A, B, and C can be 64-bit numbers?↵
I had to resort to doing ↵
↵
```c↵
inline ll prod(ll a, ll b) {↵
if (!b || !a) return 0;↵
if ((a) > (cap) / b + 1) return cap;↵
return min(a*b, cap);↵
}↵
```↵
↵
but it's obviously very slow. Also, szkopul doesn't support __int128.......↵
</spoiler>↵
↵
7. [Panini 2017](https://szkopul.edu.pl/problemset/problem/w-dbshXVyRol4LIT9jeP-bNn/site/?key=statement) [Solved Jan 19]↵
↵
<spoiler summary="Fun-ness">↵
↵
7/10↵
↵
<spoiler summary="Comments">↵
↵
This is a great problem! It feels awesome finding observations and separating this difficult-seeming problem into a few easy-to-handle cases. ↵
↵
One thing that surprised me was that I forgot an entire (fairly important) case that should've been easily caught with a random testcase but was still able to get 84 points, with only 2 subtasks showing WA. I guess this goes to show the importance of multitests, however annoying they are. ↵
↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 3e3+5;↵
↵
vector<pii> dp[maxn]; // {reaches to, cost}↵
ll smollest[maxn];↵
↵
signed main(){↵
IOS();↵
↵
int n,z,d; cin>>n>>z>>d;↵
↵
vector<ll> a(n+1);↵
vector<ll> sig(n+1);↵
↵
ll re = 0;↵
REP1(i,n) {↵
cin>>a[i];↵
if (a[i] < d) {↵
re += d-a[i]; a[i] = d;↵
}↵
if (i - z >= 0 && a[i] - a[i-z] < d) {↵
re += a[i-z] + d - a[i];↵
a[i] = a[i-z] + d;↵
}↵
bug(i, a[i]);↵
sig[i] = sig[i-1] + a[i];↵
}↵
a.pb(inf);↵
bug(re);↵
↵
dp[0].pb({0, 0});↵
↵
for (int i = 1; i<=n; ++i) {↵
ll cst = 0;↵
int ntook = 1;↵
int j = i;↵
ll base = inf;↵
for (; j>0 && ntook <= z && a[i]-a[j] <= d; --j, ++ntook) {↵
if (a[i] - a[j] == d) {↵
// try transition↵
if (dp[j][0].f <= a[j])↵
MN(base, dp[j][0].s + cst);↵
}↵
cst += a[i] - a[j];↵
}↵
↵
for (pii p : dp[j]) {↵
if (p.f <= a[i] - d) {↵
MN(base, p.s + cst);↵
}↵
}↵
↵
for (; j>0 && ntook <= z; --j, ++ntook) {↵
cst += a[i] - a[j];↵
MN(base, smollest[j-1] + cst);↵
}↵
↵
bug(i, base);↵
↵
int at = i;↵
↵
for (int rps = 0; ; ++rps) {↵
dp[at].pb({a[i] + rps * d, base});↵
ntook = 0;↵
for (; a[at] <= a[i] + (rps+1)*d && ntook <= z; ++at, ++ntook) {↵
if (ntook) {↵
base += (rps+1)*d + a[i] - a[at];↵
}↵
}↵
if (ntook == 1) break;↵
--at;↵
}↵
smollest[i] = inf;↵
for (pii p : dp[i]) {↵
MN(smollest[i], p.s);↵
}↵
sort(ALL(dp[i]), [&](pii x, pii y){return x.f!=y.f?x.f < y.f : x.s < y.s;});↵
}↵
↵
ll ret = inf;↵
↵
{↵
ret = smollest[n];↵
// for (pii p : dp[n]) MN(ret, p.s);↵
}↵
↵
cout<<ret + re<<endl;↵
↵
}↵
↵
↵
/*↵
5 5 101↵
2 100 300 400 500↵
*/↵
↵
↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
8. [Crossroads of Parity 2017](https://szkopul.edu.pl/problemset/problem/-7cqC3RrH4e-Ar7DWy4GKzLv/site/?key=statement) [Solved Jan 19]↵
↵
<spoiler summary="Fun-ness">↵
↵
7/10↵
↵
<spoiler summary="Comments (major spoilers)">↵
This was a pretty cute and nice problem! I found it pretty easy but still very nice. ↵
↵
Let $f(S)$ denote the answer after adding the set of non-MST edges $S$.↵
↵
Obviously, because of MST properties, for a non-MST edge $e$ not in $S$, $f(S \cup \{e\}) > f(S)$, but it took me a bit of time to realize (and prove) that $e_1 > e_2 \implies f(S \cup \{e_1\}) > f(S \cup \{e_2\})$, which made the problem very nice and easy. ↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
#undef BALBIT↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 5e5+5;↵
↵
struct edge{↵
int v, u, i;↵
};↵
↵
int bot[maxn]; // bottom node of each edge↵
int par[maxn]; // parent of node↵
int L[maxn],R[maxn];↵
int IT = 0;↵
vector<edge> g[maxn];↵
↵
void dfs(int v, int p) {↵
par[v] = p;↵
L[v] = R[v] = IT++;↵
for (edge e : g[v]) {↵
if (e.u != p) {↵
bot[e.i] = e.u;↵
dfs(e.u, v);↵
R[v] = R[e.u];↵
}↵
}↵
}↵
↵
vector<edge> E;↵
↵
int dpar[maxn];↵
int find(int x) {return x == dpar[x]?x : dpar[x] = find(dpar[x]);}↵
void mrg(int a, int b) {↵
a=find(a); b = find(b);↵
dpar[a] = b;↵
}↵
↵
int s[maxn];↵
int QU(int e) {↵
int re = 0;↵
for (++e; e>0; e-=e&-e) {↵
re ^= s[e];↵
}↵
return re;↵
}↵
↵
inline bool isanc(int a, int b) {↵
return L[a] <= L[b] && R[a] >= R[b];↵
}↵
↵
void MO(int e, int v) {↵
for (++e; e<maxn; e+=e&-e) {↵
s[e] ^= v;↵
}↵
}↵
↵
vector<edge> lft;↵
bool intree[maxn];↵
↵
int get(int id, ll k) { // k = 1 => find the cheapest↵
bug(id);↵
if (k > (1ll<<min(SZ(lft), 62ll))) {↵
return -1;↵
}↵
--k; // now change to binary rep↵
if (intree[id]) {↵
int bt = bot[id];↵
int re = QU(R[bt]) ^ QU(L[bt]-1);↵
REP(j, min(62ll, SZ(lft))) {↵
if (k & (1ll<<j)) {↵
re ^= isanc(bt, lft[j].u);↵
re ^= isanc(bt, lft[j].v);↵
}↵
}↵
return re;↵
}else{↵
REP(j, min(62ll, SZ(lft))) {↵
if (k & (1ll<<j)) {↵
if (lft[j].i == id) return 1;↵
}↵
}↵
return 0;↵
}↵
}↵
↵
signed main(){↵
IOS();↵
int n,m; cin>>n>>m;↵
REP(i,n) dpar[i] = i;↵
bool totpar = 0;↵
REP(i,m) {↵
int a,b; cin>>a>>b; --a; --b;↵
E.pb({a,b,i});↵
if (find(a) != find(b)) {↵
mrg(a,b);↵
g[a].pb(E.back());↵
g[b].pb({b,a,i});↵
intree[i] = 1;↵
}else {↵
lft.pb(E.back());↵
}↵
}↵
dfs(0, -1);↵
REP(i,n) {↵
int p; cin>>p;↵
MO(L[i], p); // don't forget L[i]!!!↵
}↵
↵
ll K; cin>>K;↵
↵
REP(i,m) {↵
cout<<get(i, K)<<' ';↵
}↵
↵
cout<<endl;↵
↵
int q; cin>>q;↵
while (q--) {↵
char c; cin>>c;↵
if (c == 'M') {↵
int v; cin>>v;↵
--v; MO(L[v], 1);↵
totpar ^= 1;↵
}else if (c == 'K') {↵
cin>>K;↵
}else{↵
int i; cin>>i; --i;↵
if (totpar == 1) cout<<-1<<endl;↵
else cout<<get(i,K)<<endl;↵
}↵
}↵
↵
↵
}↵
↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
9. [Hydrocontest 2016](https://szkopul.edu.pl/problemset/problem/y9HM1ctDU8V8xLMRUYACDIRs/site/?key=statement) [Solved Jan 30]↵
↵
<spoiler summary="Fun-ness">↵
↵
7/10↵
↵
<spoiler summary="Comments">↵
I enjoyed this one quite a lot. Analysis was clean and the implementation was, while difficult, not as hard as I initially thought (which was that the graph was a general cactus, with some edges on no cycles). ↵
↵
BTW, I was gone for the past week due to a participating in a camp that took quite a bit more time than I expected.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 5e5+5;↵
↵
// 1. Find all faces and label each face as a node↵
// 2. Choose a face as the root and dfs↵
// 3. After finding the answer for each node (win or lose or nothing) wrt to each face except for transition nodes, dfs again for each face and push answer down↵
// 4. Use the answers for each face wrt to each node, answer each node↵
↵
vector<int> g[maxn];↵
bool seen[maxn];↵
vector<vector<int> > face; // faces!↵
vector<vector<int> > type; // for each (face, point), find the node type here (-1 for lose, 1 for win, 0 for nothing)↵
↵
vector<int> touchface[maxn]; // faces touching this node↵
vector<int> faceval[maxn]; // values of faces touching this node,↵
↵
int par[maxn];↵
int ts[maxn]; int IT = 0;↵
↵
void dfs1(int v, int p) {↵
par[v] = p;↵
seen[v] = 1;↵
ts[v] = IT++;↵
for (int u : g[v]) {↵
if (u == p) continue; // no double edges guaranteed↵
if (seen[u]) {↵
if (ts[u] < ts[v]) {↵
// u is ancestor of v↵
vector<int> nf;↵
for (int at = v; at != u; at = par[at]) {↵
nf.pb(at);↵
}↵
nf.pb(u);↵
for (int x : nf) {↵
touchface[x].pb(SZ(face));↵
}↵
face.pb(nf);↵
type.pb({});↵
}↵
}else{↵
dfs1(u, v);↵
}↵
}↵
}↵
↵
void getans(int f, int w, int wval) { // get all the answers for face f, given that the dp for node w is wval↵
int m = SZ(face[f]);↵
vector<int> &T = type[f];↵
REP(i, m) {↵
if (T[i] == -5) {↵
T[i] = wval;↵
}↵
}↵
vector<int> ans(m); // answer for this node, facing this face↵
int nwin = 0;↵
REP(i,m) {↵
if (T[i] == 1) {↵
++nwin;↵
}↵
}↵
int lastwin = -10000000;↵
REP(i, 2*m) {↵
if (i >= m) {↵
if ((i-lastwin) < m && (i - lastwin) % 2 == 0) {↵
// win!↵
ans[i%m] = 1;↵
}↵
}↵
if (T[i%m] == 1) {↵
lastwin = i;↵
}↵
}↵
lastwin = 3*m;↵
for (int i = 2*m-1; i>=0; --i) {↵
if (i < m) {↵
if ((lastwin - i) < m && (lastwin-i)%2 == 0) {↵
ans[i] = 1;↵
}↵
}↵
if (T[i%m] == 1) lastwin = i;↵
}↵
REP(i,m) {↵
if (ans[i] == 0) {↵
if ((nwin == 0) || (nwin==1 && T[i] == 1)) {↵
// no other winning nodes left↵
ans[i] = m % 2 == 0? 2:3 ;↵
}else{↵
ans[i] = -1;↵
}↵
}↵
}↵
↵
REP(i,m) {↵
int v = face[f][i];↵
if (v == w) continue;↵
assert(SZ(touchface[v]) == SZ(faceval[v]));↵
int nwin = 0; int nflip = 0;↵
REP(j, SZ(touchface[v])) {↵
int f2 = touchface[v][j];↵
if (f2 == f) {↵
faceval[v][j] = ans[i];↵
}else{↵
assert(faceval[v][j] != -5);↵
}↵
if (faceval[v][j] == 1) ++nwin;↵
else if (faceval[v][j] == 3) ++nflip;↵
}↵
REP(j, SZ(touchface[v])) {↵
int f2 = touchface[v][j];↵
if (f2 == f) {↵
continue;↵
}↵
if (faceval[v][j] == 1) {↵
if (nwin == 1) {↵
getans(f2, v, nflip%2==1?1:2);↵
}else{↵
getans(f2, v, 1);↵
}↵
}else{↵
if (nwin) {↵
getans(f2, v, 1);↵
}else{↵
getans(f2, v, (nflip - (faceval[v][j] == 3))% 2 == 1? 1 : 2);↵
}↵
}↵
}↵
}↵
↵
}↵
↵
int dfs2(int f, int w) { // i'm at face F, working on point w. -1: losing node, 1: winning, 2: no flip node, 3: force flip node↵
int m = SZ(face[f]);↵
vector<int> &val = type[f];↵
val.resize(m,-5);↵
int wherew = -1;↵
REP(i, m) {↵
↵
int v = face[f][i];↵
// bug(f,i,w,v);↵
if (v == w) {↵
wherew = i; continue;↵
}↵
val[i] = 2;↵
vector<int> tmp;↵
for (int f2 : touchface[v]) {↵
if (f2 == f) {↵
faceval[v].pb(-5);↵
}else{↵
int gt = dfs2(f2, v);↵
faceval[v].pb(gt);↵
tmp.pb(gt);↵
}↵
}↵
for (int gt : tmp){↵
if (gt == -1 || gt == 2) continue; // no one will walk into a losing node, and no-flips do nothing↵
if (gt == 1) {↵
val[i] = 1; break; // everyone will walk a winning node!↵
}↵
if (gt == 3) {↵
val[i] ^= 1;↵
}↵
}↵
if (val[i] == 3) {↵
val[i] = 1; // winnin'↵
}↵
bug(f, i, v, val[i]);↵
}↵
↵
if (wherew == -1) {↵
// is the root↵
getans(f, -1, -1);↵
return -100;↵
}↵
↵
bool anywin = 0;↵
REP(i,m) {↵
if (val[i] == 1) {↵
anywin = 1; break;↵
}↵
}↵
↵
if (anywin == 0) {↵
return m % 2 == 0?2 : 3; // no flip or flip↵
}↵
REP1(i, m) {↵
↵
if (val[(i+wherew) % m] == 1 ) {↵
// encountered a winning node!↵
if (i % 2 == 0) {↵
return 1; // winning!↵
}↵
break;↵
}↵
}↵
↵
REP1(i, m) {↵
↵
if (val[(wherew-i+m) % m] == 1 ) {↵
// encountered a winning node!↵
if (i % 2 == 0) {↵
return 1; // winning!↵
}↵
break;↵
}↵
}↵
return -1; // there is a winning node, but the opponent will walk it↵
}↵
↵
↵
↵
signed main(){↵
IOS();↵
int n; cin>>n;↵
int m; cin>>m;↵
REP(i,m) {↵
int a,b;↵
cin>>a>>b; --a; --b;↵
g[a].pb(b); g[b].pb(a);↵
}↵
dfs1(0, -1);↵
REP(i,n) sort(ALL(touchface[i]));↵
↵
dfs2(0, -1);↵
↵
REP(i,n) {↵
bool haswin = 0;↵
int nflip = 0;↵
for (int s : faceval[i]) {↵
if (s == 1) haswin = 1;↵
else if (s == 3) {↵
++nflip;↵
}↵
}↵
if( haswin || nflip % 2 == 1) {↵
cout<<1<<endl;↵
}else{↵
cout<<2<<endl;↵
}↵
}↵
↵
↵
}↵
↵
/*↵
7 9↵
1 2↵
2 3↵
3 1↵
3 4↵
4 5↵
5 3↵
5 7↵
5 6↵
6 7↵
*/↵
↵
}↵
↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
10. [Sorcerers 2015](https://szkopul.edu.pl/problemset/problem/fuTBSUcQ2U9sVPYJUDI4JwIe/site/?key=statement)↵
11. [Direction Signs 2015](https://szkopul.edu.pl/problemset/problem/4roJ2TqCXhLN6ftK2jiWKlO9/site/?key=statement) [Solved Jan 20]↵
↵
<spoiler summary="Fun-ness">↵
↵
7/10↵
↵
<spoiler summary="Comments (major spoilers)">↵
I thought this was a nice problem, although not a very hard one (?) Maybe I've seen too many of these "The answer contains at least X% of the set" :P↵
↵
At first I wasn't sure if O(N^2 * M / 64) * 20 reps would pass, but with a couple of /2s it runs really comfortably in around 0.5s. ↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```c↵
#include <bits/stdc++.h>↵
#define int ll↵
using namespace std;↵
#define ll long long↵
#define y1 zck_is_king↵
#define pii pair<ll, ll>↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define ALL(x) x.begin(),x.end()↵
#define SZ(x) (int)x.size()↵
#define SQ(x) (x)*(x)↵
#define MN(a,b) a = min(a,(__typeof__(a))(b))↵
#define MX(a,b) a = max(a,(__typeof__(a))(b))↵
#define pb push_back↵
#define REP(i,n) for (int i = 0; i<n; ++i)↵
#define RREP(i,n) for (int i = n-1; i>=0; --i)↵
#define REP1(i,n) for (int i = 1; i<=n; ++i)↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#ifdef BALBIT↵
#define IOS()↵
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);↵
template<typename T> void _do(T &&x){cerr<<x<<endl;}↵
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}↵
#else↵
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);↵
#define endl '\n'↵
#define bug(...)↵
#endif↵
↵
const int iinf = 1e9+10;↵
const ll inf = 1ll<<60;↵
const ll mod = 1e9+7 ;↵
↵
↵
void GG(){cout<<"0\n"; exit(0);}↵
↵
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod↵
ll re=1;↵
while (n>0){↵
if (n&1) re = re*a %mo;↵
a = a*a %mo;↵
n>>=1;↵
}↵
return re;↵
}↵
↵
ll inv (ll b, ll mo = mod){↵
if (b==1) return b;↵
return (mo-mo/b) * inv(mo%b,mo) % mo;↵
}↵
↵
const int maxn = 1e5+5;↵
↵
int d[1005][202];↵
bitset<200> so[1005];↵
int R[1005];↵
↵
int from[1005], dp[1005];↵
↵
↵
signed main(){↵
IOS();↵
↵
mt19937 rnd(time(0));↵
↵
int n,m; cin>>n>>m;↵
--m;↵
REP(i,n) {↵
int r; cin>>r; R[i] = r;↵
REP(j,m) {↵
cin>>d[i][j]; d[i][j] -= r;↵
}↵
}↵
const int MAGIC = 20;↵
↵
int bst = 0;↵
vector<int>re;↵
↵
REP(qqq, MAGIC) {↵
int T = rnd()%n;↵
vector<int> same;↵
vector<pii> gv, lv;↵
REP(i,n) {↵
if (i == T) {↵
same.pb(i); continue;↵
}↵
int gr = 0;↵
int cnt = 0;↵
REP(j,m) {↵
so[i][j] = 0;↵
if (d[i][j] == d[T][j]) continue;↵
if (abs(d[i][j] - d[T][j]) >= 2) goto die;↵
↵
so[i][j] = 1; ++cnt;↵
if (d[i][j] > d[T][j]) {↵
if (gr == -1) goto die;↵
gr = 1;↵
}else{↵
if (gr == 1) goto die;↵
gr = -1;↵
}↵
}↵
↵
if (gr == 0) {↵
same.pb(i);↵
}else if (gr > 0) {↵
gv.pb({cnt,i});↵
}else{↵
lv.pb({cnt,i});↵
}↵
die:;↵
}↵
if (SZ(gv) + SZ(lv) + SZ(same) < bst) continue;↵
bug(T, bst, SZ(gv), SZ(lv), SZ(same));↵
sort(ALL(gv)); sort(ALL(lv));↵
↵
memset(from, -1, sizeof from);↵
↵
REP(i, SZ(gv)) {↵
int it = gv[i].s;↵
dp[it] = 1;↵
REP(j, i) {↵
if (dp[gv[j].s] + 1 > dp[it] && (so[it] | so[gv[j].s]) == so[it]) {↵
dp[it] = dp[gv[j].s] + 1;↵
from[it] = gv[j].s;↵
}↵
}↵
}↵
↵
↵
REP(i, SZ(lv)) {↵
int it = lv[i].s;↵
dp[it] = 1;↵
REP(j, i) {↵
if (dp[lv[j].s] + 1 > dp[it] && (so[it] | so[lv[j].s]) == so[it]) {↵
dp[it] = dp[lv[j].s] + 1;↵
from[it] = lv[j].s;↵
}↵
}↵
}↵
↵
int btog = 0;↵
int bg = -1, bl = -1;↵
for (pii G : gv) {↵
if (dp[G.s] > btog) {↵
btog = dp[G.s]; bg = G.s; bl = -1;↵
}↵
}↵
for (pii L : lv) {↵
if (dp[L.s] > btog) {↵
btog = dp[L.s]; bl = L.s; bg = -1;↵
}↵
}↵
for (pii G : gv) for (pii L : lv) {↵
if (dp[G.s] + dp[L.s] > btog && ((so[G.s] & so[L.s]).count() == 0)) {↵
btog = dp[G.s] + dp[L.s];↵
bg = G.s; bl = L.s;↵
}↵
}↵
↵
if (btog + SZ(same) > bst) {↵
vector<pair<pii, int> > rat;↵
int stp = 100000;↵
for (int at = bg; at != -1; at = from[at]) {↵
rat.pb({{R[at], stp}, at});↵
--stp;↵
}↵
stp = -100000;↵
for (int at = bl; at != -1; at = from[at]) {↵
rat.pb({{R[at], stp},at});↵
++stp;↵
}↵
↵
for (int t : same) {↵
rat.pb({{R[t], 0},t});↵
}↵
↵
sort(ALL(rat)); reverse(ALL(rat));↵
↵
assert(SZ(rat) == btog + SZ(same));↵
↵
bst = SZ(rat); re.clear();↵
↵
for (auto e : rat) {↵
re.pb(e.s+1);↵
}↵
}↵
↵
}↵
↵
cout<<SZ(re)<<endl;↵
↵
for (int x : re) cout<<x<<' ';↵
cout<<endl;↵
↵
}↵
↵
↵
/*↵
4 4↵
3 3 3 4↵
3 4 4 4↵
3 3 4 4↵
4 4 4 4↵
*/↵
↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
Note: I'll also leave comments/hints here in case I manage to solve them or (unfortunately) have to dig around CSDN for their solutions :)
