Bronze

B1

#include <bits/stdc++.h>
using namespace std;
int b[30][30];
int a[30];
int main()
{
    freopen("gymnastics.in", "r", stdin);
    freopen("gymnastics.out", "w", stdout);
    int m, n;
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &a[j]);
        }
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < j; k++)
            {
                b[a[k]][a[j]]++;
            }
        }
    }
    int ans = 0;
    for (int j = 1; j <= n; j++)
    {
        for (int k = 1; k <= n; k++)
        {
            if (b[j][k] == m)
            {
                ans++;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

B2

import sys
sys.stdin = open('whereami.in', 'r')
sys.stdout = open('whereami.out', 'w')
n = input()
s = raw_input()
for l in range(1, n + 1):
    if len(set([s[i:i+l] for i in range(n - l + 1)])) == n - l + 1:
        print l
        break

B3

#include <bits/stdc++.h>
using namespace std;
string s[8] = {"Bessie", "Buttercup", "Belinda", "Beatrice", "Bella", "Blue", "Betsy", "Sue"};
string a[7], b[7], c, d, e, f;
int n;
bool good(string a, string b)
{
    for (int i = 0; i < 7; i++)
    {
        if (s[i] == a && s[i + 1] == b)
        {
            return true;
        }
        if (s[i] == b && s[i + 1] == a)
        {
            return true;
        }
    }
    return false;
}
bool ok()
{
    for (int i = 0; i < n; i++)
    {
        if (!good(a[i], b[i]))
        {
            return false;
        }
    }
    return true;
}
int main()
{
    freopen("lineup.in", "r", stdin);
    freopen("lineup.out", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> c >> d >> e >> f >> b[i];
    }
    sort(s, s + 8);
    do
    {
        if (ok())
        {
            for (int i = 0; i < 8; i++)
            {
                cout << s[i] << endl;
            }
            break;
        }
    }
    while(next_permutation(s, s + 8));
    return 0;
}

Silver

S1

#include <bits/stdc++.h>
using namespace std;
long long calc(long long n)
{
    return n - n / 3 - n / 5 + n / 15;
}
int main()
{
    freopen("moobuzz.in", "r", stdin);
    freopen("moobuzz.out", "w", stdout);
    long long n;
    cin >> n;
    long long L = 0;
    long long R = 2 * n;
    while (L < R - 1)
    {
        int M = (L + R) / 2;
        if (calc(M) < n)
        {
            L = M;
        }
        else
        {
            R = M;
        }
    }
    cout << R << endl;
    return 0;
}

S2

#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[100020];
pair<int, int> b[100020];
pair<int, int> w[100020];
int n, l;
long long calc()
{
    long long re = 0;
    long long cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (b[i].second == -1)
        {
            cnt++;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (b[i].second == -1)
        {
            cnt--;
        }
        else
        {
            re += cnt;
        }
    }
    return re;
}
int main()
{
    freopen("meetings.in", "r", stdin);
    freopen("meetings.out", "w", stdout);
    int sum = 0, cur = 0;
    scanf("%d%d", &n, &l);
    int L = 0;
    int R = n;
    for (int i = 0; i < n; i++)
    {
        int d;
        scanf("%d%d%d", &w[i].second, &w[i].first, &d);
        b[i].first = w[i].first;
        b[i].second = d;
        sum += w[i].second;
        if (d == -1)
        {
            a[i] = make_pair(w[i].first, 0); // left;
        }
        else
        {
            a[i] = make_pair(l - w[i].first, 1); // right;
        }
    }
    sort(w, w + n);
    sort(a, a + n);
    int tim = -1;
    for (int i = 0; i < n; i++)
    {
        if (a[i].second == 0)
        {
            cur += w[L++].second;
        }
        else
        {
            cur += w[--R].second;
        }
        if (cur * 2 >= sum)
        {
            tim = a[i].first;
            break;
        }
    }
    sort(b, b + n);
    long long ans = calc();
    for (int i = 0; i < n; i++)
    {
        b[i].first += b[i].second * tim;
    }
    sort(b, b + n);
    ans -= calc();
    printf("%lld\n", ans);
    return 0;
}

S3

#include <bits/stdc++.h>
using namespace std;
int n, m;
char s[100020];
vector<int> a[100020];
int f[100020][20];
int c[100020];
int d[100020];
void dfs(int x, int y)
{
    f[x][0] = y;
    d[x] = d[y] + 1;
    c[x] = c[y] + (s[x] == 'G');
    for (int i = 1; i < 20; i++)
    {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for (int i : a[x])
    {
        if (i != y)
        {
            dfs(i, x);
        }
    }
}
int lca(int x, int y)
{
    if (d[x] < d[y])
    {
        swap(x, y);
    }
    int dd = d[x] - d[y];
    for (int i = 0; i < 20; i++)
    {
        if (dd >> i & 1)
        {
            x = f[x][i];
        }
    }
    if (x == y)
    {
        return x;
    }
    for (int i = 20 - 1; i >= 0; i--)
    {
        if (f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    freopen("milkvisits.in", "r", stdin);
    freopen("milkvisits.out", "w", stdout);
    scanf("%d%d", &n, &m);
    scanf("%s", s + 1);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 0);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        char o[2];
        scanf("%d%d%s", &x, &y, o);
        int l = lca(x, y);
        int dxy = d[x] + d[y] - 2 * d[l] + 1;
        int cxy = c[x] + c[y] - 2 * c[l] + (s[l] == 'G');
        if (o[0] == 'G')
        {
            printf("%d", cxy > 0);
        }
        else
        {
            printf("%d", cxy < dxy);
        }
    }
    printf("\n");
    return 0;
}

Gold

G1

#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<pair<int, int>, pair<int, int> > b[1020];
vector<pair<int, int> > a[1020];
priority_queue<pair<int, int> > q;
int d[100020];
int dijk()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    q.push(make_pair(-d[1], 1));
    while (q.size() > 0)
    {
        pair<int, int> u = q.top();
        q.pop();
        if (-u.first > d[u.second])
        {
            continue;
        }
        for (int i = 0; i < a[u.second].size(); i++)
        {
            pair<int, int> e = a[u.second][i];
            if (d[e.first] > d[u.second] + e.second)
            {
                d[e.first] = d[u.second] + e.second;
                q.push(make_pair(-d[e.first], e.first));
            }
        }
    }
    return d[n];
}
int main()
{
    freopen("pump.in", "r", stdin);
    freopen("pump.out", "w", stdout);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> b[i].second.first >> b[i].second.second >> b[i].first.second >> b[i].first.first;
    }
    sort(b, b + m);
    long long ans = 0;
    for (int i = m - 1; i >= 0; i--)
    {
        a[b[i].second.first].push_back(make_pair(b[i].second.second, b[i].first.second));
        a[b[i].second.second].push_back(make_pair(b[i].second.first, b[i].first.second));
        ans = max(ans, 1000000LL * b[i].first.first / dijk());
    }
    cout << ans << endl;
    return 0;
}

G2

#include <bits/stdc++.h>
using namespace std;
int n, m;
int cl[100020];
vector<int> cc[100020];
vector<int> a[100020];
int f[100020][20];
int c[100020];
int d[100020];
int L[100020];
int R[100020];
int s[100020], ss;
char z[100020];
vector<pair<pair<int, int>, int> > q[100020];
void change(int x, int y)
{
    for (; x <= n; x += x & -x)
    {
        c[x] += y;
    }
}
int query(int x)
{
    int re = 0;
    for (; x > 0; x -= x & -x)
    {
        re += c[x];
    }
    return re;
}
void dfs(int x, int y)
{
    L[x] = ss;
    s[ss++] = x;
    f[x][0] = y;
    d[x] = d[y] + 1;
    for (int i = 1; i < 20; i++)
    {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for (int i : a[x])
    {
        if (i != y)
        {
            dfs(i, x);
        }
    }
    R[x] = ss;
}
int lca(int x, int y)
{
    if (d[x] < d[y])
    {
        swap(x, y);
    }
    int dd = d[x] - d[y];
    for (int i = 0; i < 20; i++)
    {
        if (dd >> i & 1)
        {
            x = f[x][i];
        }
    }
    if (x == y)
    {
        return x;
    }
    for (int i = 20 - 1; i >= 0; i--)
    {
        if (f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    freopen("milkvisits.in", "r", stdin);
    freopen("milkvisits.out", "w", stdout);
    ss = 1;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &cl[i]);
        cc[cl[i]].push_back(i);
    }
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 0);
    for (int i = 0; i < m; i++)
    {
        int x, y, o;
        scanf("%d%d%d", &x, &y, &o);
        q[o].push_back(make_pair(make_pair(x, y), i));
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < cc[i].size(); j++)
        {
            change(L[cc[i][j]], 1);
            change(R[cc[i][j]], -1);
        }
        for (int j = 0; j < q[i].size(); j++)
        {
            int x = q[i][j].first.first;
            int y = q[i][j].first.second;
            int l = lca(x, y);
            int cnt = query(L[x]) + query(L[y]) - 2 * query(L[l]) + (cl[l] == i);
            z[q[i][j].second] = (cnt > 0) + '0';
        }
        for (int j = 0; j < cc[i].size(); j++)
        {
            change(L[cc[i][j]], -1);
            change(R[cc[i][j]], 1);
        }
    }
    printf("%s\n", z);
    return 0;
}

G3

#include <bits/stdc++.h>
using namespace std;
int n, m, l;
char c[100020];
int s[100020][30];
int f[100020][30];
int a[30][30];
int main()
{
    freopen("cowmbat.in", "r", stdin);
    freopen("cowmbat.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &l);
    scanf("%s", c + 1);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    for (int k = 0; k < m; k++)
    {
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (a[i][j] > a[i][k] + a[k][j])
                {
                    a[i][j] = a[i][k] + a[k][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            s[i][j] = s[i - 1][j] + a[c[i] - 'a'][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            f[i][j] = f[i - 1][j] + a[c[i] - 'a'][j];
        }
        if (i >= l)
        {
            int tmp = 1e9;
            for (int j = 0; j < m; j++)
            {
                tmp = min(tmp, f[i - l][j] + s[i][j] - s[i - l][j]);
            }
            for (int j = 0; j < m; j++)
            {
                f[i][j] = min(f[i][j], tmp);
            }
            if (i == n)
            {   
                printf("%d\n", tmp);
            }
        }
    }
    return 0;
}

Platinum

P1

#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[320][320][9][9];
int a[320][320];
int g[320][320];
int fastlg[320];
int query(int x1, int y1, int x2, int y2)
{
    int dx = fastlg[x2 - x1 + 1], dy = fastlg[y2 - y1 + 1];
    return max(max(f[x1][y1][dx][dy], f[x2 - (1 << dx) + 1][y1][dx][dy]), max(f[x1][y2 - (1 << dy) + 1][dx][dy], f[x2 - (1 << dx) + 1][y2 - (1 << dy) + 1][dx][dy]));
}
int main()
{
    freopen("pieaters.in", "r", stdin);
    freopen("pieaters.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 2; i < 310; i++)
    {
        fastlg[i] = fastlg[i / 2] + 1;
    }
    for (int i = 0; i < m; i++)
    {
        int z, x, y;
        scanf("%d%d%d", &z, &x, &y);
        x--;
        y--;
        a[x][y] = z;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            f[i][j][0][0] = a[i][j];
        }
    }
    for (int k = 0; 1 << k <= n; k++)
        for (int l = 0; 1 << l <= n; l++)
            if (k + l)
                for (int i = 0; i + (1 << k) <= n; i++)
                    for (int j = 0; j + (1 << l) <= n; j++)
                    {
                        if (k)
                        {
                            f[i][j][k][l] = max(f[i][j][k - 1][l], f[i + (1 << (k - 1))][j][k - 1][l]);
                        }
                        else
                        {
                            f[i][j][k][l] = max(f[i][j][k][l - 1], f[i][j + (1 << (l - 1))][k][l - 1]);
                        }
                    }
    for (int l = 0; l < n; l++)
    {
        for (int i = 0; i + l < n; i++)
        {
            int j = i + l;
            for (int k = i; k < j; k++)
            {
                g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j]);
            }
            for (int k = i + 1; k < j; k++)
            {
                g[i][j] = max(g[i][j], g[i][k - 1] + g[k + 1][j] + query(i, k + 1, k - 1, j));
            }
            g[i][j] = max(g[i][j], g[i][j - 1] + query(i, j, j, j));
            g[i][j] = max(g[i][j], g[i + 1][j] + query(i, i, i, j));
        }
    }
    printf("%d\n", g[0][n - 1]);
    return 0;
}

P2

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[100020];
int L[100020];
int R[100020];
int s[100020], ss;
int sz[100020];
char z[100020];
set<pair<int, int> > op[100020];

long long tsz[400020];
long long sm[400020];
int tmd[400020];
void build(int x, int l, int r)
{
    if (l + 1 == r)
    {
        tsz[x] = 1;
        return;
    }
    int m = (l + r) / 2;
    build(2 * x, l, m);
    build(2 * x + 1, m, r);
    tsz[x] = tsz[2 * x] + tsz[2 * x + 1];
}
void push(int x)
{
    tmd[2 * x] += tmd[x];
    sm[2 * x] += tsz[2 * x] * tmd[x];
    tmd[2 * x + 1] += tmd[x];
    sm[2 * x + 1] += tsz[2 * x + 1] * tmd[x];
    tmd[x] = 0;
}
void change(int x, int l, int r, int L, int R, int v)
{
    // if (x == 1)
    // printf("change %d %d %d %d %d %d\n", x, l, r, L, R, v);
    if (r <= L || R <= l)
    {
        return;
    }
    if (L <= l && r <= R)
    {
        tmd[x] += v;
        sm[x] += tsz[x] * v;
        return;
    }
    push(x);
    int m = (l + r) / 2;
    change(2 * x, l, m, L, R, v);
    change(2 * x + 1, m, r, L, R, v);
    sm[x] = sm[2 * x] + sm[2 * x + 1];
}
long long query(int x, int l, int r, int L,int R)
{
    // printf("query %d %d %d %d %d\n", x, l, r, L, R);
    if (r <= L || R <= l)
    {
        return 0;
    }
    if (L <= l && r <= R)
    {
        return sm[x];
    }
    push(x);
    int m = (l + r) / 2;
    return query(2 * x, l, m, L, R) + query(2 * x + 1, m, r, L, R);
}

void dfs(int x, int y)
{
    L[x] = ss;
    s[ss++] = x;
    sz[x] = 1;
    for (int i : a[x])
    {
        if (i != y)
        {
            dfs(i, x);
            sz[x] += sz[i];
        }
    }
    R[x] = ss;
}

int main()
{
    freopen("snowcow.in", "r", stdin);
    freopen("snowcow.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 0);
    build(1, 0, n);
    for (int i = 0; i < m; i++)
    {
        int x, y, o;
        scanf("%d", &o);
        if (o == 1)
        {
            scanf("%d%d", &x, &y);
            set<pair<int, int> >::iterator it = op[y].upper_bound(make_pair(L[x], R[x]));
            if (it != op[y].begin())
            {
                if ((--it)->second >= R[x])
                {
                    continue;
                }
            }
            while (true)
            {
                set<pair<int, int> >::iterator it = op[y].upper_bound(make_pair(L[x], R[x]));
                if (it == op[y].end() || R[x] <= it->first)
                {
                    break;
                }
                change(1, 0, n, it->first, it->second, -1);
                op[y].erase(it);
            }
            change(1, 0, n, L[x], R[x], 1);
            op[y].insert(make_pair(L[x], R[x]));
        }
        else
        {
            scanf("%d", &x);
            printf("%lld\n", query(1, 0, n, L[x], R[x]));
        }
    }
    return 0;
}

P3

#include <bits/stdc++.h>
using namespace std;
int n, m, mod;

int fs[320][45020];
int gs[320][45020];
int hs[320][45020];
int ans2[320];
int ans3[320];
int F(int x, int y)
{
    int re = fs[x][y + 1] - fs[x][y];
    if (re < 0)
    {
        re += mod;
    }
    return re;
}
int G(int x, int y)
{
    int re = gs[x][y + 1] - gs[x][y];
    if (re < 0)
    {
        re += mod;
    }
    return re;
}
int H(int x, int y)
{
    int re = hs[x][y + 1] - hs[x][y];
    if (re < 0)
    {
        re += mod;
    }
    return re;
}
void caonima()
{
    // f[len][inversion] = sum of such number;
    // g[len][inversion] = the number of such permutation;
    memset(fs, 0, sizeof fs);
    memset(gs, 0, sizeof gs);
    memset(hs, 0, sizeof hs);
    for (int j = 0; j <= n * (n - 1) / 2; j++)
    {
        gs[1][j + 1] = (gs[1][j] + (j == 0)) % mod;
    }

    for (int i = 2; i <= n; i++)
    {
        int fucklimit = i * (i - 1) / 2;
        for (int j = 0; j <= fucklimit; j++)
        {
            int kk = max(j - (i - 2), 0);
            int nf = (fs[i - 1][j + 1] - fs[i - 1][kk] + mod) % mod;
            int ng = (gs[i - 1][j + 1] - gs[i - 1][kk] + mod) % mod;
            if (j - (i - 1) >= 0)
            {
                nf = ((long long)nf + F(i - 1, j - (i - 1)) + G(i - 1, j - (i - 1))) % mod;
                ng = (ng + G(i - 1, j - (i - 1))) % mod;
            }
            fs[i][j + 1] = (fs[i][j] + nf) % mod;
            gs[i][j + 1] = (gs[i][j] + ng) % mod;
        }
        for (int j = fucklimit + 1; j <= n * (n - 1) / 2; j++)
        {
            fs[i][j + 1] = (fs[i][j]) % mod;
            gs[i][j + 1] = (gs[i][j]) % mod;
        }
    }
    for (int j = 0; j <= n * (n - 1) + 1; j++)
    {
        hs[0][j + 1] = (hs[0][j] + (j == 0)) % mod;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= n * (n - 1) / 2; j++)
        {
            int kk = max(0, j - (n - i));
            int nh = (hs[i - 1][j + 1] - hs[i - 1][kk] + mod) % mod;
            hs[i][j + 1] = (hs[i][j] + nh) % mod;
        }
    }
}

void gao3()
{
    caonima();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            // cerr << i << " " << j << " " << h[i][j] << " " << f[n - i][m - j] << endl;
            ans3[i] = (ans3[i] + (long long)H(i, j) * F(n - i, m - j)) % mod;
        }
    }
    m = n * (n - 1) / 2 - m;
    caonima();
    reverse(ans3, ans3 + n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            // cerr << i << " " << j << " " << h[i][j] << " " << f[n - i][m - j] << endl;
            ans3[i] = (ans3[i] + (long long)H(i, j) * F(n - i, m - j)) % mod;
        }
    }
    reverse(ans3, ans3 + n);
    m = n * (n - 1) / 2 - m;
    for (int i = 0; i < n; i++)
    {
        ans3[i] = (ans3[i] + H(n, m)) % mod;
    }
}

int main()
{
    freopen("treedepth.in", "r", stdin);
    freopen("treedepth.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &mod);
    // gao1();
    // for (int i = 0; i < n; i++)
    // {
    //  printf("%d%c", ans1[i], i == n - 1 ? '\n' : ' ');
    // }
    // gao2();
    // for (int i = 0; i < n; i++)
    // {
    //  printf("%d%c", ans2[i], i == n - 1 ? '\n' : ' ');
    // }
    gao3();
    for (int i = 0; i < n; i++)
    {
        printf("%d%c", ans3[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}