Codeforces Round #558 (Div. 2) Editorial
Difference between en2 and en3, changed 0 character(s)
Hello everyone, this is the editorial for [contest:1163]. I hope you enjoy the problem as well as I did!↵

[problem:1163A]↵

Author: [user:_iloveNQ_,2019-05-09]↵

<spoiler summary="Tutorial">↵
[tutorial:1163A]↵
</spoiler>↵

<spoiler summary="Implementation">↵
~~~~~↵
#include <iostream>↵

using namespace std;↵

int main ()↵
{↵
    int n, m;↵
cin >> n >> m;↵
cout << (m ? min(m, n - m) : 1) << endl;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵



[problem:1163B2]↵

Author: [user:_Shirone_,2019-05-09]↵

<spoiler summary="Tutorial">↵
[tutorial:1163B2]↵
</spoiler>↵

<spoiler summary="Implementation">↵
~~~~~↵
#include <iostream>↵
#include <stdio.h>↵
using namespace std;↵

const int N = 1e5 + 10;↵

int n, color, ans, mx, f[N], cnt[N];↵

int main()↵
{↵
scanf("%d", &n);↵
for (int i = 1; i <= n; i++)↵
    {↵
        scanf("%d", &color);↵
        cnt[f[color]]--;↵
        f[color]++;↵
        cnt[f[color]]++;↵
        mx = max(mx, f[color]);↵
        bool ok = false;↵
        if (cnt[1] == i) // every color has occurence of 1↵
            ok = true;↵
        else if (cnt[i] == 1) // only one color has the maximum occurence and the occurence is i↵
            ok = true;↵
        else if (cnt[1] == 1 && cnt[mx] * mx == i - 1) // one color has occurence of 1 and other colors have the same occurence↵
            ok = true;↵
        else if (cnt[mx - 1] * (mx - 1) == i - mx && cnt[mx] == 1) // one color has the occurence 1 more than any other color↵
            ok = true;↵
        if (ok)↵
            ans = i;↵
    }↵
    printf("%d", ans);↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵



[problem:1163C2]↵

Author: [user:LunarStellarshot,2019-05-09]↵

<spoiler summary="Tutorial">↵
[tutorial:1163C2]↵
</spoiler>↵

<spoiler summary="Implementation">↵
~~~~~↵
#include <cstdio>↵
#include <map>↵
#include <set>↵
#include <utility>↵
const int N = 1001;↵
int x[N], y[N];↵
std::map<std::pair<int,int>,std::set<long long>> slope_map;↵

int gcd(int a, int b) ↵
{↵
if (a == 0)↵
return b;↵
return gcd(b % a, a);↵
}↵

int main()↵
{↵
int n; scanf("%d", &n);↵
for (int i = 1; i <= n; ++i)↵
scanf("%d%d", &x[i], &y[i]);↵
long long total = 0, res = 0;↵
for (int i = 1; i <= n - 1; ++i)↵
for (int j = i + 1; j <= n; ++j)↵
{↵
int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j];↵
// construct a line passing through (x1, y1) and (x2, y2)↵
// line is expressed as equation ax - by = c with constant a, b, c ↵
int a = y1 - y2, b = x1 - x2;↵
// simplify equation↵
int d = gcd(a, b); a /= d, b /= d;↵
if (a < 0 || (a == 0 && b < 0))↵
{↵
    a = -a;↵
    b = -b;↵
}↵
// lines with the same slope (same a, b) are stored in a map↵
std::pair<int,int> slope(a, b);↵
long long c = 1LL * a * x1 - 1LL * b * y1;↵
if (!slope_map[slope].count(c))↵
{↵
++total;↵
slope_map[slope].insert(c);↵
// if this line is new, it intersects every line with different slope↵
res += total - slope_map[slope].size();↵
}↵
}↵
printf("%lld\n", res);↵
}↵
~~~~~↵
</spoiler>↵



[problem:1163D]↵

Author: [user:_Kuroni_,2019-05-09]↵

<spoiler summary="Tutorial">↵
[tutorial:1163D]↵
</spoiler>↵

<spoiler summary="Implementation">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <cstring>↵
using namespace std;↵

const int K = 1005, N = 55, M = 55, INF = 1E9 + 7;↵

int k, n, m;↵
int kmp_s[N], nxt_s[N][26], kmp_t[M], nxt_t[M][26];↵
int dp[K][N][M];↵
char code[K], s[N], t[M];↵

void init(char s[], int n, int kmp[], int nxt[][26])↵
{↵
    kmp[1] = 0;↵
    for (int i = 2; i <= n; i++)↵
    {↵
        int cur = kmp[i - 1];↵
        while (cur > 0 && s[cur + 1] != s[i])↵
            cur = kmp[cur];↵
        if (s[cur + 1] == s[i])↵
            ++cur;↵
        kmp[i] = cur;↵
    }↵

    for (int i = 0; i <= n; i++)↵
        for (char c = 'a'; c <= 'z'; c++)↵
        {↵
            int cur = i;↵
            while (cur > 0 && s[cur + 1] != c)↵
                cur = kmp[cur];↵
            if (s[cur + 1] == c)↵
                ++cur;↵
            nxt[i][c - 'a'] = cur;↵
        }↵
}↵

int main()↵
{↵
    scanf("%s%s%s", code + 1, s + 1, t + 1);↵
    k = strlen(code + 1); n = strlen(s + 1); m = strlen(t + 1);↵
    init(s, n, kmp_s, nxt_s); init(t, m, kmp_t, nxt_t);↵
    for (int i = 0; i <= k; i++)↵
        for (int ks = 0; ks <= n; ks++)↵
            for (int kt = 0; kt <= m; kt++)↵
                dp[i][ks][kt] = -INF;↵
    dp[0][0][0] = 0;↵
    for (int i = 0; i < k; i++)↵
        for (int ks = 0; ks <= n; ks++)↵
            for (int kt = 0; kt <= m; kt++)↵
                for (char c = 'a'; c <= 'z'; c++)↵
                    if (code[i + 1] == '*' || code[i + 1] == c) // we now add/replace the (i + 1)-th character↵
                    {↵
                        int ns = nxt_s[ks][c - 'a'], nt = nxt_t[kt][c - 'a'];↵
                        int tmp = dp[i][ks][kt] + (ns == n) - (nt == m); // add the new occurrences if any↵
                        dp[i + 1][ns][nt] = max(dp[i + 1][ns][nt], tmp);↵
                    }↵
    int ma = -INF;↵
    for (int ks = 0; ks <= n; ks++)↵
        for (int kt = 0; kt <= m; kt++)↵
            ma = max(ma, dp[k][ks][kt]);↵
    printf("%d\n", ma);↵
}↵
~~~~~↵
</spoiler>↵



[problem:1163E]↵

Author: [user:_Kuroni_,2019-05-09]↵

<spoiler summary="Tutorial">↵
[tutorial:1163E]↵
</spoiler>↵

<spoiler summary="Implementation">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <vector>↵
#include <algorithm>↵
using namespace std;↵

const int N = 200005;↵

int n, a[N];↵
vector<int> basis, vec;↵

void add(int u)↵
{↵
    int tmp = u;↵
    // we keep the basis sorted in decreasing order↵
    for (int &v : basis)↵
        u = min(u, u ^ v);↵
    if (u > 0) // u is a new element in the basis↵
    {↵
        basis.push_back(u);↵
        vec.push_back(tmp);↵
        // now we move u up until the basis is decreasingly sorted again↵
        for (int i = basis.size() - 1; i > 0; i--)↵
            if (basis[i] > basis[i - 1])↵
                swap(basis[i], basis[i - 1]);↵
            else↵
                break;↵
    }↵
}↵

void gray_code(int size)↵
{↵
    vector<int> ans = {0};↵
    for (int i = 0; i < size; i++)↵
        for (int j = (1 << i) - 1; j >= 0; j--)↵
            ans.push_back(ans[j] ^ vec[i]);↵
    for (int &v : ans)↵
        printf("%d ", v);↵
}↵

int main()↵
{↵
    scanf("%d", &n);↵
    for (int i = 0; i < n; i++)↵
        scanf("%d", a + i);↵
    sort(a, a + n);↵
    int pt = 0, x = 0;↵
    for (int i = 1; i < 20; i++)↵
    {↵
        for (; pt < n && a[pt] < (1 << i); pt++)↵
            add(a[pt]);↵
        if (basis.size() == i)↵
            x = i;↵
    }↵
    basis.clear();↵
    vec.clear();↵
    for (int i = 0; i < n && a[i] < (1 << x); i++)↵
        add(a[i]);↵
    printf("%d\n", x);↵
    gray_code(x);↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Implementation with DFS">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <vector>↵
#include <algorithm>↵
using namespace std;↵

const int N = 200005, MX = 1E6 + 5;↵

int n, x = 0, a[N];↵
bool vis[MX];↵
vector<int> basis, vec, ans;↵

void add(int u)↵
{↵
    int tmp = u;↵
    for (int &v : basis)↵
        u = min(u, u ^ v);↵
    if (u > 0)↵
    {↵
        basis.push_back(u);↵
        vec.push_back(tmp);↵
        for (int i = basis.size() - 1; i > 0; i--)↵
            if (basis[i] > basis[i - 1])↵
                swap(basis[i], basis[i - 1]);↵
            else↵
                break;↵
    }↵
}↵

void DFS(int u, int it = 0)↵
{↵
    ans.push_back(u);↵
    vis[u] = true;↵
    if (it == (1 << x) - 1)↵
        return;↵
    for (int &v : vec)↵
        if (!vis[u ^ v])↵
        {↵
            DFS(u ^ v, it + 1);↵
            return;↵
        }↵
}↵

int main()↵
{↵
    scanf("%d", &n);↵
    for (int i = 0; i < n; i++)↵
        scanf("%d", a + i);↵
    sort(a, a + n);↵
    int pt = 0;↵
    for (int i = 1; i < 20; i++)↵
    {↵
        for (; pt < n && a[pt] < (1 << i); pt++)↵
            add(a[pt]);↵
        if (basis.size() == i)↵
            x = i;↵
    }↵
    basis.clear();↵
    vec.clear();↵
    for (int i = 0; i < n && a[i] < (1 << x); i++)↵
        add(a[i]);↵
    printf("%d\n", x);↵
    DFS(0);↵
    for (int &v : ans)↵
        printf("%d ", v);↵
}↵
~~~~~↵
</spoiler>↵



[problem:1163F]↵

Author: [user:_Kuroni_,2019-05-09]↵

<spoiler summary="Tutorial">↵
[tutorial:1163F]↵
</spoiler>↵

<spoiler summary="Implementation">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <vector>↵
#include <queue>↵
using namespace std;↵

const int N = 2E5 + 5, M = 2E5 + 5;↵
const long long INF = 1E18 + 7;↵

int n, m, q, ed, nw, mx, u[M], v[M], w[M], ind[M];↵
int tr[N], le[N], ri[N];↵
bool on_path[N];↵
long long dis[2][N];↵

struct TNode↵
{↵
    int u;↵
    long long val;↵

    TNode(int _u, long long _val)↵
    {↵
        u = _u;↵
        val = _val;↵
    }↵

    inline bool operator>(const TNode &oth) const↵
    {↵
        return val > oth.val;↵
    }↵
};↵
priority_queue<TNode, vector<TNode>, greater<TNode>> pq;↵

struct TEdge↵
{↵
    int v, w, ind;↵

    TEdge(int _v, int _w, int _ind)↵
    {↵
        v = _v;↵
        w = _w;↵
        ind = _ind;↵
    }↵
};↵
vector<TEdge> adj[N];↵

struct TTree↵
{↵
#define m (l + r) / 2↵
#define lc i * 2↵
#define rc i * 2 + 1↵

    long long tr[4 * M];↵

    void build(int l, int r, int i)↵
    {↵
        tr[i] = INF;↵
        if (l == r)↵
            return;↵
        build(l, m, lc);↵
        build(m + 1, r, rc);↵
    }↵

    void upd(int l, int r, int i, int L, int R, long long v)↵
    {↵
        if (l > R || r < L || L > R)↵
            return;↵
        if (L <= l && r <= R)↵
        {↵
            tr[i] = min(tr[i], v);↵
            return;↵
        }↵
        upd(l, m, lc, L, R, v);↵
        upd(m + 1, r, rc, L, R, v);↵
    }↵

    long long que(int l, int r, int i, int u)↵
    {↵
        if (l == r)↵
            return tr[i];↵
        return min(tr[i], u <= m ? que(l, m, lc, u) : que(m + 1, r, rc, u));↵
    }↵

#undef m↵
#undef lc↵
#undef rc↵
} seg;↵

void dijkstra(int st, long long dis[], int get = 0)↵
{↵
    fill(dis + 1, dis + n + 1, INF);↵
    pq.push(TNode(st, dis[st] = 0));↵
    while (!pq.empty())↵
    {↵
        TNode u = pq.top(); pq.pop();↵
        if (u.val > dis[u.u])↵
            continue;↵
        for (TEdge &v : adj[u.u])↵
            if (dis[v.v] > u.val + v.w)↵
            {↵
                tr[v.v] = v.ind;↵
                if (get == 1 && !on_path[v.v])↵
                    le[v.v] = le[u.u];↵
                else if (get == 2 && !on_path[v.v])↵
                    ri[v.v] = ri[u.u];↵
                pq.push(TNode(v.v, dis[v.v] = u.val + v.w));↵
            }↵
    }↵
}↵

void trace()↵
{↵
    on_path[1] = true; le[1] = ri[1] = 0;↵
    for (int i = 1, cur = 1; cur != n; i++)↵
    {↵
        int edge = tr[cur];↵
        ind[edge] = mx = i;↵
        cur = u[edge] ^ v[edge] ^ cur;↵
        on_path[cur] = true;↵
        le[cur] = ri[cur] = i;↵
    }↵
}↵

int main()↵
{↵
    scanf("%d%d%d", &n, &m, &q);↵
    for (int i = 1; i <= m; i++)↵
    {↵
        scanf("%d%d%d", u + i, v + i, w + i);↵
        ind[i] = -1;↵
        adj[u[i]].push_back(TEdge(v[i], w[i], i));↵
        adj[v[i]].push_back(TEdge(u[i], w[i], i));↵
    }↵
    dijkstra(n, dis[1]); // reverse the initial dijkstra for the trace to increase from 1 -> n↵
    trace();↵
    dijkstra(1, dis[0], 1);↵
    dijkstra(n, dis[1], 2);↵
    seg.build(1, mx, 1);↵
    for (int i = 1; i <= m; i++)↵
        if (ind[i] == -1)↵
        {↵
            seg.upd(1, mx, 1, le[u[i]] + 1, ri[v[i]], dis[0][u[i]] + w[i] + dis[1][v[i]]);↵
            seg.upd(1, mx, 1, le[v[i]] + 1, ri[u[i]], dis[0][v[i]] + w[i] + dis[1][u[i]]);↵
        }↵
    while (q--)↵
    {↵
        scanf("%d%d", &ed, &nw);↵
        long long ans;↵
        if (ind[ed] > 0)↵
        {↵
            ans = dis[0][n] - w[ed] + nw;↵
            if (nw > w[ed])↵
                ans = min(ans, seg.que(1, mx, 1, ind[ed]));↵
        }↵
        else↵
        {↵
            ans = dis[0][n];↵
            if (nw < w[ed])↵
            {↵
                ans = min(ans, dis[0][u[ed]] + nw + dis[1][v[ed]]);↵
                ans = min(ans, dis[0][v[ed]] + nw + dis[1][u[ed]]);↵
            }↵
        }↵
        printf("%lld\n", ans);↵
    }↵
}↵
~~~~~↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Kuroni 2019-05-09 20:51:10 0 (published)
en2 English Kuroni 2019-05-09 20:37:00 22
en1 English Kuroni 2019-05-09 20:32:56 12254 Initial revision (saved to drafts)