Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2) —— Editorial
Разница между en1 и en2, 1,986 символ(ов) изменены
[tutorial:1017A]↵

<spoiler summary="Solution(arsijo)">↵

~~~~~↵

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

int main()↵
{↵
    int n;↵
cin >> n;↵
int a, b, c, d;↵
cin >> a >> b >> c >> d;↵
int S = a + b + c + d;↵
int Ans = 1;↵
for(int i = 2; i <= n; i++)↵
{↵
    cin >> a >> b >> c >> d;↵
    if(a + b + c + d > S)↵
    {↵
        Ans++;↵
    }↵
}↵
printf("%d\n",Ans);↵
return 0;↵
}↵

~~~~~↵

</spoiler>↵


[tutorial:1017B]↵

<spoiler summary="Solution(arsijo)">↵

~~~~~↵

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

long long ar[4];↵
char c1[4] = {'0', '0', '1', '1'};↵
char c2[4] = {'0', '1', '0', '1'};↵

int main() {↵
    int n;↵
    cin >> n;↵
    string a, b;↵
    cin >> a >> b;↵
    for(int i = 0; i < n; i++){↵
        for(int j = 0; j < 4; j++){↵
            if(c1[j] == a[i] && c2[j] == b[i]){↵
                ar[j]++;↵
            }↵
        }↵
    }↵
    cout << ar[0] * ar[2] + ar[0] * ar[3] + ar[1] * ar[2] << endl;↵
    return 0;↵
}↵

~~~~~↵

</spoiler>↵

[tutorial:1017C]↵

<spoiler summary="Solution(Magolor)">↵

~~~~~↵

#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 100000↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
int n, L, A[MAXN+5];↵
int main()↵
{↵
n = rf();↵
L = (int)sqrt(n);↵
for(rint i = 1, o = n, j; i <= n; i += L)↵
for(j = min(i+L-1,n); j >= i; A[j--] = o--);↵
for(rint i = 1; i <= n; i++)↵
printf("%d%c",A[i],"\n "[i<n]);↵
return 0;↵
}↵

~~~~~↵

</spoiler>↵

[tutorial:1017D]↵

<spoiler summary="Solution(Magolor)">↵

~~~~~↵

#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 100000↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
int Wu[4096], f[64][64][104], g[4096][104], w[16], m, n, q, E, K, B = 6, L = 63, H = 4032; char _[16];↵
int main()↵
{↵
m = rf();↵
n = rf();↵
q = rf();↵
generate(w,w+m,rf);↵
E = 1<<m;↵
for(rint S = 0, j; S < E; S++)↵
{↵
for(j = 0; j < m; j++)↵
S&1<<j?:Wu[S]+=w[j];↵
Wu[S] = min(Wu[S],101);↵
}↵
for(rint i = 1, j, S; i <= n; i++)↵
{↵
scanf("%s",_+1);↵
for(S = 0, j = m; j; j--)↵
S = S<<1|(_[j]^'0');↵
for(j = 0; j < 64; j++)↵
++f[(S&H)>>B][j][Wu[((j^(S&L))|H)&~-E]];↵
}↵
for(rint S = 0, a, b, j; S < E; S++)↵
{↵
for(j = 0; j < 64; j++)↵
for(a = 0, b = Wu[(((j<<B)^(S&H))|L)&~-E]; b <= 100; a++, b++)↵
g[S][b] += f[j][S&L][a];↵
partial_sum(g[S],g[S]+101,g[S]);↵
}↵
for(rint i = 1, j, S; i <= q; i++)↵
{↵
scanf("%s",_+1);↵
for(S = 0, j = m; j; j--)↵
S = S<<1|(_[j]^'0');↵
printf("%d\n",g[S][rf()]);↵
}↵
return 0;↵
}↵

~~~~~↵

</spoiler>↵

[tutorial:1017E]↵

<spoiler summary="Solution(Magolor)">↵

~~~~~↵

#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
//=====Computational Geometry Definitions↵
struct Vec↵
{↵
int x,y; Vec(){} Vec(int _x, int _y){x=_x,y=_y;} inline Vec operator + (Vec b){return Vec(x+b.x,y+b.y);}↵
inline Vec operator - (Vec b){return Vec(x-b.x,y-b.y);} inline Vec operator - (){return Vec(-x,-y);}↵
inline ll operator * (Vec b){return (ll)x*b.x+(ll)y*b.y;} inline ll operator % (Vec b){return (ll)x*b.y-(ll)b.x*y;}↵
inline ll operator ~ (){return (ll)x*x+(ll)y*y;} inline bool operator < (const Vec &b)const{return x^b.x?x<b.x:y<b.y;}↵
inline bool operator ==(Vec b){return x==b.x&&y==b.y;} inline bool operator !=(Vec b){return x^b.x||y^b.y;}↵
}; typedef Vec Pt; inline bool ToLeft(Vec a, Vec b){return b%a>0;} inline bool Para(Vec a, Vec b){return !(a%b);}↵
Pt LTL; inline bool cmpltl(Pt a, Pt b){a = a-LTL; b = b-LTL; return Para(a,b) ? ~a<~b : ToLeft(b,a);}↵
typedef vector<Pt> Poly; Poly A, B, C, D; typedef vector<ll> Str; Str T, S; int n, m; vector<int> nex;↵
//=====↵
void CH(Poly &A, Poly &R)↵
{↵
R.push_back(Pt());↵
LTL = *min_element(A.begin(),A.end());↵
sort(A.begin(),A.end(),cmpltl);↵
for(rint i = 0; i < (int)A.size(); i++)↵
{↵
for(; R.size()>2&&!ToLeft(A[i]-R.back(),R.back()-R[R.size()-2]); )↵
R.pop_back();↵
R.push_back(A[i]);↵
}↵
R[0] = R[R.size()-1];↵
R.push_back(R[1]);↵
}↵
void CTOS(Poly &p, Str &s)↵
{↵
s.push_back(0);↵
for(rint i = 1; i < (int)p.size()-1; i++)↵
{↵
s.push_back(~(p[i]-p[i-1]));↵
s.push_back((p[i]-p[i-1])%(p[i+1]-p[i]));↵
}↵
}↵
void CalNex()↵
{↵
nex.resize(m+1);↵
for(rint i = 2, j = 1; i <= m; i++)↵
{↵
for(; j>1&&S[i]^S[j]; )↵
j = nex[j-1]+1;↵
j += S[i]==S[j];↵
nex[i] = j-1;↵
}↵
}↵
bool KMP()↵
{↵
for(rint i = 1, j = 1; i <= n; i++)↵
{↵
for(; j>1&&(j>m||T[i]^S[j]); )↵
j = nex[j-1]+1;↵
j+=T[i]==S[j]; ↵
if(j>m)↵
return true;↵
}↵
return false;↵
}↵
int main()↵
{↵
A.resize(rf()); B.resize(rf());↵
for(rint i = 0, s = (int)A.size(); i < s; i++)↵
A[i].x = rf(), A[i].y = rf();↵
CH(A,C);↵
CTOS(C,T);↵
n = T.size()-1;↵
for(rint i = 0, s = (int)B.size(); i < s; i++)↵
B[i].x = rf(), B[i].y = rf();↵
CH(B,D);↵
CTOS(D,S);↵
m = S.size()-1;↵
for(rint i = 1, s = (int)T.size(); i < s; i++)↵
T.push_back(T[i]);↵
n <<= 1;↵
CalNex();↵
puts(KMP()?"YES":"NO");↵
return 0;↵
}↵

~~~~~↵

</spoiler>↵

<spoiler summary="Solution(Kostroma)">↵

~~~~~↵

#pragma comment(linker, "/STACK:512000000")↵
#define _CRT_SECURE_NO_WARNINGS↵
//#include "testlib.h"↵
#include <bits/stdc++.h>↵
using namespace std;↵

#define all(a) a.begin(), a.end()↵
using li = long long;↵
using ld = long double;↵
void solve(bool);↵
void precalc();↵
clock_t start;↵
int main() {↵
#ifdef AIM↵
  freopen("/home/alexandero/CLionProjects/ACM/input.txt", "r", stdin);↵
//freopen("/home/alexandero/CLionProjects/ACM/output.txt", "w", stdout);↵
//freopen("out.txt", "w", stdout);↵
#else↵
  //freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
#endif↵
  start = clock();↵
  int t = 1;↵
#ifndef AIM↵
  cout.sync_with_stdio(0);↵
  cin.tie(0);↵
#endif↵
  cout.precision(20);↵
  cout << fixed;↵
//cin >> t;↵
  precalc();↵
  while (t--) {↵
    solve(true);↵
  }↵
  cout.flush();↵

#ifdef AIM1↵
  while (true) {↵
solve(false);↵
}↵
#endif↵

#ifdef AIM↵
  cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";↵
#endif↵
  return 0;↵
}↵

//BE CAREFUL: IS INT REALLY INT?↵

template<typename T>↵
T binpow(T q, T w, T mod) {↵
  if (!w)↵
    return 1 % mod;↵
  if (w & 1)↵
    return q * 1LL * binpow(q, w - 1, mod) % mod;↵
  return binpow(q * 1LL * q % mod, w / 2, mod);↵
}↵

template<typename T>↵
T gcd(T q, T w) {↵
  while (w) {↵
    q %= w;↵
    swap(q, w);↵
  }↵
  return q;↵
}↵
template<typename T>↵
T lcm(T q, T w) {↵
  return q / gcd(q, w) * w;↵
}↵

template <typename T>↵
void make_unique(vector<T>& vec) {↵
  sort(all(vec));↵
  vec.erase(unique(all(vec)), vec.end());↵
}↵

template<typename T>↵
void relax_min(T& cur, T val) {↵
  cur = min(cur, val);↵
}↵

template<typename T>↵
void relax_max(T& cur, T val) {↵
  cur = max(cur, val);↵
}↵

void precalc() {↵

}↵

#define int li↵
//const li mod = 1000000007;↵
//using ull = unsigned long long;↵

struct Point {↵
  int x, y;↵
  Point() {}↵
  Point(int x, int y) : x(x), y(y) {}↵
  Point operator - (const Point& ot) const {↵
    return Point(x - ot.x, y - ot.y);↵
  }↵
  int operator * (const Point& ot) const {↵
    return x * ot.y - y * ot.x;↵
  }↵
  void scan() {↵
    cin >> x >> y;↵
  }↵
  bool operator < (const Point& ot) const {↵
    return make_pair(x, y) < make_pair(ot.x, ot.y);↵
  }↵
  int sqr_len() const {↵
    return x * x + y * y;↵
  }↵
  long double get_len() const {↵
    return sqrtl(sqr_len());↵
  }↵
  int operator % (const Point& ot) const {↵
    return x * ot.x + y * ot.y;↵
  }↵
};↵

struct Polygon {↵
  vector<Point> hull;↵
  Polygon(int n) {↵
    vector<Point> points(n);↵
    for (int i = 0; i < n; ++i) {↵
      points[i].scan();↵
    }↵
    sort(all(points));↵
    vector<Point> up, down;↵
    for (auto& pt : points) {↵
      while (up.size() > 1 && (up[up.size() - 2] - up.back()) * (pt - up.back()) >= 0) {↵
        up.pop_back();↵
      }↵
      up.push_back(pt);↵
      while (down.size() > 1 && (down[down.size() - 2] - down.back()) * (pt - down.back()) <= 0) {↵
        down.pop_back();↵
      }↵
      down.push_back(pt);↵
    }↵
    hull = up;↵
    for (int i = (int)down.size() - 2; i > 0; --i) {↵
      hull.push_back(down[i]);↵
    }↵
  }↵
  int sqr_len(int pos) const {↵
    return (hull[(pos + 1) % hull.size()] - hull[pos]).sqr_len();↵
  }↵
  int size() const {↵
    return (int)hull.size();↵
  }↵
  long double get_angle(int pos) const {↵
    auto a = hull[(pos + 1) % hull.size()] - hull[pos], b = hull[(pos + hull.size() - 1) % hull.size()] - hull[pos];↵
    long double co = (a % b) / a.get_len() / b.get_len();↵
    return co;↵
  }↵
};↵

void solve(bool read) {↵
  vector<Polygon> polys;↵
  int n[2];↵
  cin >> n[0] >> n[1];↵
  for (int i = 0; i < 2; ++i) {↵
    polys.emplace_back(n[i]);↵
  }↵
  if (polys[0].size() != polys[1].size()) {↵
    cout << "NO\n";↵
    return;↵
  }↵
  vector<long double> all_lens;↵
  int m = polys[0].size();↵
  for (int i = 0; i < m; ++i) {↵
    all_lens.push_back(polys[0].sqr_len(i));↵
    all_lens.push_back(polys[0].get_angle(i));↵
  }↵
  all_lens.push_back(-1);↵
  for (int j = 0; j < 2; ++j) {↵
    for (int i = 0; i < m; ++i) {↵
      all_lens.push_back(polys[1].sqr_len(i));↵
      all_lens.push_back(polys[1].get_angle(i));↵
    }↵
  }↵
  /*for (int x : all_lens) {↵
    cout << x << " ";↵
  }↵
  cout << "\n";*/↵
  vector<int> p(all_lens.size());↵
  for (int i = 1; i < p.size(); ++i) {↵
    int j = p[i - 1];↵
    while (j > 0 && all_lens[i] != all_lens[j]) {↵
      j = p[j - 1];↵
    }↵
    if (all_lens[i] == all_lens[j]) {↵
      ++j;↵
    }↵
    p[i] = j;↵
    if (p[i] == 2 * m) {↵
      cout << "YES\n";↵
      return;↵
    }↵
  }↵
  cout << "NO\n";↵

}↵

~~~~~↵

</spoiler>↵


[tutorial:1017F]↵

<spoiler summary="Solution(Magolor,optimized by arsijo)">↵

~~~~~↵

#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define uint unsigned int↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
bitset<100000032> _b; int n; uint A, B, C, D, Ans;↵
inline uint f(int p){↵
    return((A*p+B)*p+C)*p+D;↵
}↵
inline int cnt(int p, int n){↵
    int r=0;↵
    for(;n/=p;r+=n);↵
    return r;↵
}↵
inline auto b(int i)->decltype(_b[0]){↵
    return _b[(i&1)&&(i%6!=3)?i/6<<1|((i%6)>1):0];↵
}↵
inline auto b2(int i)->decltype(_b[0]){↵
    return _b[i/6<<1|1];↵
}↵
inline auto b3(int i)->decltype(_b[0]){↵
    return _b[i/6<<1];↵
}↵

int main()↵
{↵
    n = rf();↵
    A = rf();↵
    B = rf();↵
    C = rf();↵
    D = rf();↵
    _b[0] = 1;↵
    Ans = cnt(2,n)*f(2)+cnt(3,n)*f(3);↵
    for(rint i = 5, j, z, c, w; i <= n; i += 4){↵
        if(!b2(i))↵
        {↵
            Ans += cnt(i,n)*f(i);↵
            if(i <= 20000){↵
                w = i + i;↵
                c = w % 6;↵
                z = (i * i) % 6;↵
                if(c == 0){↵
                    if(z == 1){↵
                        for(j = i * i; j <= n; j += w){↵
                            b3(j) = 1;↵
                        }↵
                    }else if(z == 5){↵
                        for(j = i * i; j <= n; j += w){↵
                            b2(j) = 1;↵
                        }↵
                    }↵
                }else if(c == 2){↵
                    if(z == 1){↵
                        for(j = i * i; j <= n; j += w){↵
                            b3(j) = 1;↵
                            j += w + w;↵
                            if(j <= n){↵
                                b2(j) = 1;↵
                            }↵
                        }↵
                    }else if(z == 5){↵
                        for(j = i * i; j <= n; j += w + w){↵
                            b2(j) = 1;↵
                            j += w;↵
                            if(j <= n){↵
                                b3(j) = 1;↵
                            }↵
                        }↵
                    }↵
                }else if(c == 4){↵
                    if(z == 1){↵
                        for(j = i * i; j <= n; j += w + w){↵
                            b3(j) = 1;↵
                            j += w;↵
                            if(j <= n){↵
                                b2(j) = 1;↵
                            }↵
                        }↵
                    }else if(z == 5){↵
                        for(j = i * i; j <= n; j += w){↵
                            b2(j) = 1;↵
                            j += w + w;↵
                            if(j <= n){↵
                                b3(j) = 1;↵
                            }↵
                        }↵
                    }↵
                }↵
            }↵
        }↵
        i += 2;↵
        if(i <= n && !b3(i))↵
        {↵
            Ans += cnt(i,n)*f(i);↵
            if(i <= 20000){↵
                w = i + i;↵
                c = w % 6;↵
                z = (i * i) % 6;↵
                if(c == 0){↵
                    if(z == 1){↵
                        for(j = i * i; j <= n; j += w){↵
                            b3(j) = 1;↵
                        }↵
                    }else if(z == 5){↵
                        for(j = i * i; j <= n; j += w){↵
                            b2(j) = 1;↵
                        }↵
                    }↵
                }else if(c == 2){↵
                    if(z == 1){↵
                        for(j = i * i; j <= n; j += w){↵
                            b3(j) = 1;↵
                            j += w + w;↵
                            if(j <= n){↵
                                b2(j) = 1;↵
                            }↵
                        }↵
                    }else if(z == 5){↵
                        for(j = i * i; j <= n; j += w + w){↵
                            b2(j) = 1;↵
                            j += w;↵
                            if(j <= n){↵
                                b3(j) = 1;↵
                            }↵
                        }↵
                    }↵
                }else if(c == 4){↵
                    if(z == 1){↵
                        for(j = i * i; j <= n; j += w + w){↵
                            b3(j) = 1;↵
                            j += w;↵
                            if(j <= n){↵
                                b2(j) = 1;↵
                            }↵
                        }↵
                    }else if(z == 5){↵
                        for(j = i * i; j <= n; j += w){↵
                            b2(j) = 1;↵
                            j += w + w;↵
                            if(j <= n){↵
                                b3(j) = 1;↵
                            }↵
                        }↵
                    }↵
                }↵
            }↵
        }↵
    }↵
    printf("%u\n",Ans);↵
    return 0;↵
}↵

~~~~~↵

</spoiler>↵

<spoiler summary="Solution(000000)">↵

~~~~~↵

#include <bits/stdc++.h>↵

using namespace std;↵
typedef unsigned int ll;↵
const ll maxn=4e8;↵
const ll maxp=sqrt(maxn)+10;↵
ll f[4][maxp],g[4][maxp];↵
ll n,m,A,B,C,D,ans,res,tmp,rt;↵

ll p1(ll x){↵
    ll y=x+1; if (x%2==0) x/=2; else y/=2;↵
    return x*y;↵
}↵
ll p2(ll x){↵
    long long y=x+1,z=x*2+1;↵
    if (x%2==0) x/=2; else y/=2;↵
    if (z%3==0) z/=3; else if (x%3==0) x/=3; else y/=3;↵
    return (ll)x*y*z;↵
}↵
ll p3(ll x){↵
    ll y=p1(x);↵
    return y*y;↵
}↵
bool is_prime(ll x){↵
    for (ll i=2;i*i<=x;i++) if (x%i==0) return false;↵
    return true;↵
}↵

ll solve(ll n)↵
{↵
    ll i,j,rt,o[4];↵
    for (m=1;m*m<=n;m++) {↵
        f[0][m]=(n/m-1);↵
        f[1][m]=(p1(n/m)-1)*C;↵
        f[2][m]=(p2(n/m)-1)*B;↵
        f[3][m]=(p3(n/m)-1)*A;↵
    }↵
    for (i=1;i<=m;i++) {↵
        g[0][i]=(i-1);↵
        g[1][i]=(p1(i)-1)*C;↵
        g[2][i]=(p2(i)-1)*B;↵
        g[3][i]=(p3(i)-1)*A;↵
    }↵
    for (i=2;i<=m;i++) {↵
        if (g[0][i]==g[0][i-1]) continue;↵
        o[0]=1; for (int w=1;w<4;w++) o[w]=o[w-1]*i;↵
        for (j=1;j<=min(m-1,n/i/i);j++)↵
            for (int w=0;w<4;w++)↵
                if (i*j<m) f[w][j]-=o[w]*(f[w][i*j]-g[w][i-1]);↵
                else f[w][j]-=o[w]*(g[w][n/i/j]-g[w][i-1]);↵
        for (j=m;j>=i*i;j--)↵
            for (int w=0;w<4;w++)↵
                g[w][j]-=o[w]*(g[w][j/i]-g[w][i-1]);↵
    }↵
    for (int i=1;i<=m+1;i++) f[0][i]*=D,g[0][i]*=D;↵
    rt=0;↵
    for (ll i=1;n/i>m;i++) {↵
        for (int w=0;w<4;w++) rt+=(f[w][i]-g[w][m]);↵
        //cout<<"H"<<rt<<endl;↵
    }↵
    return rt;↵
}↵

int main()↵
{↵
    //freopen("input.txt","r",stdin);↵
    ll n; cin >> n >> A >> B >> C >> D;↵
    ans=solve(n);↵
    for (ll i=2;i<=m;i++){↵
        if (is_prime(i)){↵
            res=A*i*i*i+B*i*i+C*i+D; tmp=n;↵
            while (tmp){↵
                ans+=res*(tmp/i);↵
                tmp/=i;↵
            }↵
        }↵
    }↵
    cout << ans << endl;↵
    return 0;↵
}↵

~~~~~↵

</spoiler>↵


[tutorial:1017G]↵

<spoiler summary="Solution(arsijo)">↵

~~~~~↵

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

const int MAX = 1e5 + 10;↵

bool black[MAX]; // is it vertex black now↵
vector<int> vec[MAX]; // main edges↵
bool old_black[MAX]; // to remember the tree before block↵

const int MAX_BLOCK_SIZE = 600;↵

int t[MAX], v[MAX]; // queries↵

bool used[MAX]; // is in mini-tree↵
vector<pair<pair<int, int>, int> > v2[MAX]; // mini-tree edges (son, number of white vertices, dist)↵
int push[MAX]; // push of the i-th vertex in mini-tree↵
bool clear[MAX]; // do we need to clear first↵

void dfs_1(int pos, int prev = -1, int white = 0, int dist = 0){↵
    if(used[pos]){↵
        if(prev != -1){↵
            v2[prev].push_back(make_pair(make_pair(pos, white), dist));↵
        }↵
        for(int a : vec[pos]){↵
            dfs_1(a, pos, 0, 0);↵
        }↵
    }else{↵
        if(!black[pos]){↵
            white++;↵
        }↵
        for(int a : vec[pos]){↵
            dfs_1(a, prev, white, dist + 1);↵
        }↵
    }↵
}↵

void make_1(int pos){↵
    if(!black[pos]){↵
        black[pos] = true;↵
        return;↵
    }↵
    push[pos]++;↵
    for(auto a : v2[pos]){↵
        if(a.first.second + 1 <= push[pos]){↵
            make_1(a.first.first);↵
        }↵
    }↵
}↵

void make_2(int pos){↵
    black[pos] = false;↵
    push[pos] = 0;↵
    clear[pos] = true;↵
    for(auto &a : v2[pos]){↵
        a.first.second = a.second;↵
        make_2(a.first.first);↵
    }↵
}↵

void dfs_2(int pos, int p = 0, bool cl = false){↵
    if(used[pos]){↵
        p = push[pos];↵
        cl |= clear[pos];↵
    }else{↵
        black[pos] = old_black[pos];↵
        if(cl){↵
            black[pos] = false;↵
        }↵
        if(!black[pos] && p){↵
            black[pos] = true;↵
            p--;↵
        }↵
    }↵
    for(int a : vec[pos]){↵
        dfs_2(a, p, cl);↵
    }↵
}↵

int main(){↵
    ios_base::sync_with_stdio();↵
    cin.tie(0);↵
    cout.tie(0);↵
    int n, q;↵
    cin >> n >> q;↵
    for(int i = 2; i <= n; i++){↵
        int a;↵
        cin >> a;↵
        vec[a].push_back(i);↵
    }↵
    for(int i = 1; i <= q; i++){↵
        cin >> t[i] >> v[i];↵
    }↵
    int root = 1;↵
    for(int i = 1; i <= q; i += MAX_BLOCK_SIZE){↵
        for(int j = 1; j <= n; j++){↵
            used[j] = false;↵
            v2[j].clear();↵
            old_black[j] = black[j];↵
            push[j] = 0;↵
            clear[j] = false;↵
        }↵
        for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){↵
            used[v[i + j]] = true;↵
        }↵
        dfs_1(root);↵
        for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){↵
            int t = ::t[i + j];↵
            int v = ::v[i + j];↵
            if(t == 1){↵
                make_1(v);↵
            }else if(t == 2){↵
                make_2(v);↵
            }else{↵
                cout << (black[v] ? "black" : "white") << "\n";↵
            }↵
        }↵
        dfs_2(root);↵
    }↵
    return 0;↵
}↵

~~~~~↵

</spoiler>↵

[tutorial:1017H]↵

<spoiler summary="Solution(Magolor)">↵

~~~~~↵

#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 200000↵
#define MOD 998244353↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
int n, m, q, B, C, T, fac[MAXN+5], efac[MAXN+5], Ans[MAXN+5], A[MAXN+5], t[MAXN+5], c[MAXN+5];↵
int mp[MAXN+5], rv[480], h[480][100032], _init[MAXN+5], d[105][100032]; bitset<100032> b[480];↵
typedef pair<int,int> pii; pii S[MAXN+5]; struct QU{int u,l,r,k,i;}Q[MAXN+5];↵
inline bool cmpi(const QU &a, const QU &b)↵
{↵
return a.i<b.i;↵
}↵
inline bool cmpm(const QU &a, const QU &b)↵
{↵
return a.u^b.u?a.u<b.u:a.u&1?a.r<b.r:a.r>b.r;↵
}↵
//fastpow↵
inline int fxp(int s, int n=MOD-2){int a=1;for(;n;n&1?a=1ll*a*s%MOD:0,s=1ll*s*s%MOD,n>>=1);return a;}↵
inline void Init(int k)↵
{↵
if(_init[k]) return;↵
_init[k] = ++C;↵
int *D = d[C], s = 1ll*m*k%MOD;↵
D[0] = 1;↵
for(rint i = 1; i <= n; i++)↵
D[i] = 1ll*D[i-1]*(s+i)%MOD;↵
}↵
inline int dxp(int a, int b)↵
{↵
return 1ll*fac[a]*efac[a-b]%MOD;↵
}↵
inline int DXP(int k, int l)↵
{↵
return d[_init[k]][l]; ↵
}↵
void insert(int x)↵
{↵
--h[t[x]][c[x]++];↵
++h[t[x]][c[x]];↵
S[++T] = pii(t[x],c[x]);↵
}↵
void erase(int x)↵
{↵
--h[t[x]][c[x]--];↵
++h[t[x]][c[x]];↵
S[++T] = pii(t[x],c[x]);↵
}↵
inline int calc(int k)↵
{↵
int _ = T; T = 0;↵
for(rint i = 1; i <= _; i++)↵
if(!b[S[i].first][S[i].second]&&h[S[i].first][S[i].second])↵
S[++T] = S[i], b[S[i].first][S[i].second] = 1;↵
int Ans = 1;↵
for(rint i = 1; i <= T; i++)↵
{↵
b[S[i].first][S[i].second] = 0;↵
Ans = 1ll*Ans*fxp(dxp(rv[S[i].first]+k,S[i].second),h[S[i].first][S[i].second])%MOD;↵
}↵
return Ans;↵
}↵
int main()↵
{↵
n = MAXN;↵
for(rint i = fac[0] = 1; i <= n; i++)↵
fac[i] = 1ll*i*fac[i-1]%MOD;↵
efac[n] = fxp(fac[n]);↵
for(rint i = n; i; i--)↵
efac[i-1] = 1ll*i*efac[i]%MOD;↵
n = rf();↵
m = rf();↵
q = rf();↵
B = n/sqrt(q*2/3)+1;↵
for(rint i = 1; i <= n; i++)↵
++t[A[i]=rf()];↵
for(rint i = 1, c = 0; i <= n; i++)↵
mp[t[A[i]]]?:rv[mp[t[A[i]]]=++c]=t[A[i]];↵
for(rint i = 1; i <= m; i++)↵
t[i] = mp[t[i]];↵
for(rint i = 1, l, r, k; i <= q; i++)↵
{↵
l = rf();↵
r = rf();↵
k = rf();↵
Init(k);↵
Q[i] = {~-l/B,l,r,k,i};↵
}↵
sort(Q+1,Q+q+1,cmpm);↵
for(rint i = 1; i <= n; i++)↵
++h[t[A[i]]][0];↵
for(rint i = 1, l = 1, r = 0; i <= q; i++)↵
{↵
for(; l > Q[i].l; insert(A[--l]));↵
for(; r < Q[i].r; insert(A[++r]));↵
for(; l < Q[i].l; erase(A[l++]));↵
for(; r > Q[i].r; erase(A[r--]));↵
Ans[Q[i].i] = calc(Q[i].k);↵
}↵
sort(Q+1,Q+q+1,cmpi);↵
for(rint i = 1; i <= q; i++)↵
printf("%d\n",1ll*DXP(Q[i].k,n-(Q[i].r-Q[i].l+1))*Ans[i]%MOD);↵
return 0;↵
}↵

~~~~~↵

</spoiler>↵


<spoiler summary="Solution(Kostroma)">↵

~~~~~↵

#pragma comment(linker, "/STACK:512000000")↵
#include <bits/stdc++.h>↵
using namespace std;↵

#define all(a) a.begin(), a.end()↵
typedef long long li;↵
typedef long double ld;↵
void solve(__attribute__((unused)) bool);↵
void precalc();↵
clock_t start;↵
#define FILENAME ""↵

int main() {↵
#ifdef AIM↵
    string s = FILENAME;↵
//    assert(!s.empty());↵
    freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);↵
  //freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout);↵
#else↵
//    freopen(FILENAME ".in", "r", stdin);↵
//    freopen(FILENAME ".out", "w", stdout);↵
    //freopen("input.txt", "r", stdin);↵
    //freopen("output.txt", "w", stdout);↵
#endif↵
    start = clock();↵
    int t = 1;↵
#ifndef AIM↵
    cout.sync_with_stdio(0);↵
    cin.tie(0);↵
#endif↵
  precalc();↵
    cout.precision(10);↵
    cout << fixed;↵
    //cin >> t;↵
    int testNum = 1;↵
    while (t--) {↵
        //cout << "Case #" << testNum++ << ": ";↵
        solve(true);↵
    }↵
    cout.flush();↵
#ifdef AIM1↵
    while (true) {↵
      solve(false);↵
  }↵
#endif↵

#ifdef AIM↵
    cout.flush();↵
    auto end = clock();↵

    usleep(10000);↵
    print_stats(end - start);↵
    usleep(10000);↵
#endif↵

    return 0;↵
}↵

template<typename T>↵
T binpow(T q, T w, T mod) {↵
    if (!w)↵
        return 1 % mod;↵
    if (w & 1)↵
        return q * 1LL * binpow(q, w - 1, mod) % mod;↵
    return binpow(q * 1LL * q % mod, w / 2, mod);↵
}↵

template<typename T>↵
T gcd(T q, T w) {↵
    while (w) {↵
        q %= w;↵
        swap(q, w);↵
    }↵
    return q;↵
}↵
template<typename T>↵
T lcm(T q, T w) {↵
    return q / gcd(q, w) * w;↵
}↵

template <typename T>↵
void make_unique(vector<T>& a) {↵
    sort(all(a));↵
    a.erase(unique(all(a)), a.end());↵
}↵

template<typename T>↵
void relax_min(T& cur, T val) {↵
    cur = min(cur, val);↵
}↵

template<typename T>↵
void relax_max(T& cur, T val) {↵
    cur = max(cur, val);↵
}↵

void precalc() {↵
}↵

#define int li↵
const int mod = 998244353;↵

struct Query {↵
  int l, r, id;↵
};↵

vector<int> res;↵
vector<int> a;↵
int n;↵

int TIMER = 0;↵
const int C = 200500;↵
int used[C];↵
int cur_cnt[C];↵
int rev[C];↵
map<int, vector<int>> down;↵
vector<int> init;↵

void kill(vector<Query>& all_q, int block_size, int k) {↵
  vector<vector<Query>> by_block(n / block_size + 1);↵
  for (auto& cur_q : all_q) {↵
    by_block[cur_q.l / block_size].push_back(cur_q);↵
  }↵
  for (int i = 0; i < by_block.size(); ++i) {↵
    ++TIMER;↵
    auto& q = by_block[i];↵
    sort(all(q), [&] (const Query& o1, const Query& o2) {↵
      return o1.r < o2.r;↵
    });↵
    int cur_l = min(n, (i + 1) * block_size);↵
    int cur_r = cur_l;↵
    int cur_prod = 1;↵

    auto add_item = [&] (int val) {↵
      if (used[val] != TIMER) {↵
        used[val] = TIMER;↵
        cur_cnt[val] = 0;↵
      }↵
      int cur_k = k + init[val];↵
      ++cur_cnt[val];↵
        cur_prod = cur_prod * (cur_k - cur_cnt[val] + 1) % mod;↵
    };↵
    auto remove_item = [&] (int val) {↵
      int cur_k = k + init[val];↵
        cur_prod = cur_prod * rev[cur_k - cur_cnt[val] + 1] % mod;↵
      --cur_cnt[val];↵
    };↵

    for (auto& cur_q : q) {↵
      while (cur_r < cur_q.r) {↵
        add_item(a[cur_r++]);↵
      }↵
      while (cur_l > cur_q.l) {↵
        add_item(a[--cur_l]);↵
      }↵
      while (cur_r > cur_q.r) {↵
        remove_item(a[--cur_r]);↵
      }↵
      while (cur_l < cur_q.l) {↵
        remove_item(a[cur_l++]);↵
      }↵
        res[cur_q.id] = cur_prod * down[k][n - cur_q.r + cur_q.l] % mod;↵
    }↵
  }↵
}↵

void solve(__attribute__((unused)) bool read) {↵
  for (int i = 1; i < C; ++i) {↵
    rev[i] = binpow(i, mod - 2, mod);↵
  }↵
  int m, Q;↵
  //read = false;↵
  if (read) {↵
    cin >> n >> m >> Q;↵
  } else {↵
    n = 50000;↵
    m = 100000;↵
    Q = 50000;↵
  }↵
  a.resize(n);↵
  init.assign(m, 0);↵
  for (int i = 0; i < n; ++i) {↵
    if (read) {↵
      cin >> a[i];↵
      --a[i];↵
    } else {↵
      a[i] = rand() % m;↵
    }↵
    ++init[a[i]];↵
  }↵
  map<int, vector<Query>> q;↵
  for (int i = 0; i < Q; ++i) {↵
    int l, r, k;↵
    if (read) {↵
      cin >> l >> r >> k;↵
    } else {↵
      do {↵
        l = rand() % n + 1;↵
        r = rand() % n + 1;↵
      } while (l > r);↵
      k = rand() % 100;↵
    }↵
    --l;↵
    q[k].push_back({l, r, i});↵
    down[k] = vector<int>();↵
  }↵
  res.assign(Q, 0);↵
  for (auto& item : down) {↵
    int init_val = (item.first * m) % mod;↵
    auto& vec = item.second;↵
    vec.assign(n + 1, 1);↵
    for (int i = 1; i < vec.size(); ++i) {↵
      vec[i] = vec[i - 1] * (init_val + i) % mod;↵
    }↵
  }↵
  for (auto& item : q) {↵
    int k = item.first;↵
    auto& cur_q = item.second;↵
    int block_size = std::max((int)(n / sqrt((int)cur_q.size())), 1LL);↵
    kill(cur_q, block_size, k);↵
  }↵

  for (int i = 0; i < Q; ++i) {↵
    cout << res[i] << "\n";↵
  }↵

}↵

~~~~~↵

</spoiler>↵

### Bonus Problem↵
It is the previous D1E and its standard solution is hacked. Can you solve it?↵

<spoiler summary="Bonus problem">↵

**Legend**↵

How can the man in the high castle, Abendsen, escape so many times? Because he has a full plan of escaping —— with his films.↵

The map of the cities can be described as a tree (i.e. connected graph with $n$ vertices and $n-1$ edges) rooted at node $1$ —— where Abenden lives.↵

When he starts his escaping, he plans **at most** $k$ travels: one travel is a simple path between two (not necessarily different) vertices. So he goes from $1$ to some vertex $v_1$, and then goes from $v_1$ to $v_2$, and so on $\ldots$↵

When he is visiting a vertex (even though he has visited this vertex before) he will get some films. But in some vertexes, he has to give some films. Note that Abendsen \textbf{can} have a negative amount of films. But after every travel, he **has to have a non-negative amount of films**. Note that when Abendsen is starting a new travel, **he is visiting the starting vertex too**. It sounds weird but it is a different world!↵

At first, Abendsen does not have any films.↵

He wants to maximize the number of the films he gets after the escape. So please help him find out the maximized films number he can get.↵

**Input Format**↵

The first line two contains two integers $n$ and $k$ ($1 \le n \le 1000$, $1 \le k \le 10^6$) —— the number of vertices and the maximum number of travels allowed.↵

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($|w_i|\leq 10^8$) —— how many films will Abendsen get (or give if $w_i$ is negative) if he visits the $i$-th vertex.↵

Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$ ($1\leq u_i, v_i\leq n$, $u_i\neq v_i$) —— vertices connected by the $i$-th edge.↵

It is guaranteed that the input data describes a correct tree.↵

**Output Format**↵

Print one integer, the maximum number of films he can get.↵


</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Magolor 2018-08-08 21:40:38 1986
en1 Английский Magolor 2018-08-08 21:28:09 27934 Initial revision (published)