Codeforces Round #722 Editorial
Difference between en19 and en20, changed 2 character(s)
Hello, Codeforces!↵


[problem:1529A]↵

problem idea and solution: [user:AmShZ,2021-05-24]↵

<spoiler summary="editorial">↵
[tutorial:1529A]↵
</spoiler>↵


<spoiler summary="official solution">↵
~~~~~↵
// khodaya khodet komak kon↵
# include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
typedef long long                                        ll;↵
typedef long double                                      ld;↵
typedef pair <int, int>                                  pii;↵
typedef pair <pii, int>                                  ppi;↵
typedef pair <int, pii>                                  pip;↵
typedef pair <pii, pii>                                  ppp;↵
typedef pair <ll, ll>                                    pll;↵
 ↵
# define A                                               first↵
# define B                                               second↵
# define endl                                            '\n'↵
# define sep                                             ' '↵
# define all(x)                                          x.begin(), x.end()↵
# define kill(x)                                         return cout << x << endl, 0↵
# define SZ(x)                                           int(x.size())↵
# define lc                                              id << 1↵
# define rc                                              id << 1 | 1↵
 ↵
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}↵
 ↵
const int xn = 1e2 + 10;↵
const int xm = &mdash; 20 + 10;↵
const int sq = 320;↵
const int inf = 1e9 + 10;↵
const ll INF = 1e18 + 10;↵
const int mod = 1e9 + 7;//998244353;↵
const int base = 257;↵
 ↵
int qq, n, a[xn], mn, ans;↵
 ↵
int main(){↵
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);↵
cin >> qq;↵
while (qq --){↵
cin >> n, mn = inf, ans = 0;↵
for (int i = 1; i <= n; ++ i)↵
cin >> a[i], mn = min(mn, a[i]);↵
for (int i = 1; i <= n; ++ i)↵
ans += a[i] != mn;↵
cout << ans << endl;↵
}↵
 ↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵












[problem:1529B]↵

problem idea and solution: [user:-zeus-,2021-05-24]↵

<spoiler summary="editorial">↵
[tutorial:1529B]↵
</spoiler>↵


<spoiler summary="official solution">↵

~~~~~↵
// khodaya khodet komak kon↵
// Nightcall - London Grammer↵
# include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
typedef long long                                        ll;↵
typedef long double                                      ld;↵
typedef pair <int, int>                                  pii;↵
typedef pair <pii, int>                                  ppi;↵
typedef pair <int, pii>                                  pip;↵
typedef pair <pii, pii>                                  ppp;↵
typedef pair <ll, ll>                                    pll;↵
 ↵
# define A                                               first↵
# define B                                               second↵
# define endl                                            '\n'↵
# define sep                                             ' '↵
# define all(x)                                          x.begin(), x.end()↵
# define kill(x)                                         return cout << x << endl, 0↵
# define SZ(x)                                           int(x.size())↵
# define lc                                              id << 1↵
# define rc                                              id << 1 | 1↵
 ↵
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}↵
 ↵
const int xn = 1e5 + 10;↵
const int xm = - 20 + 10;↵
const int sq = 320;↵
const int inf = 1e9 + 10;↵
const ll INF = 1e18 + 10;↵
const int mod = 1e9 + 7;//998244353;↵
const int base = 257;↵
 ↵
int qq, n, a[xn], ans, mn;↵
bool flag;↵
 ↵
int main(){↵
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);↵
 ↵
cin >> qq;↵
while (qq --){↵
cin >> n, ans = 0;↵
for (int i = 1; i <= n; ++ i)↵
cin >> a[i], ans += (a[i] <= 0);↵
sort(a + 1, a + n + 1), mn = inf;↵
for (int i = 1; i <= n; ++ i)↵
if (a[i] > 0)↵
mn = min(mn, a[i]);↵
flag = (mn < inf);↵
for (int i = 2; i <= n; ++ i)↵
if (a[i] <= 0)↵
flag &= (a[i] - a[i - 1] >= mn);↵
if (flag)↵
cout << ans + 1 << endl;↵
else↵
cout << ans << endl;↵
}↵
 ↵
return 0;↵
}↵
~~~~~↵

</spoiler>↵











[problem:1528A]↵

problem idea and solution: [user:Mahdi_Shokoufi,2021-05-24], [user:AmShZ,2021-05-24]↵

<spoiler summary="editorial">↵
[tutorial:1528A]↵
</spoiler>↵


<spoiler summary="official solution">↵

~~~~~↵
// Call my Name and Save me from The Dark↵
#include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
typedef long long int ll;↵
typedef pair<int, int> pii;↵
 ↵
#define SZ(x)                       (int) x.size()↵
#define F                           first↵
#define S                           second↵
 ↵
const int N = 2e5 + 10;↵
ll dp[2][N]; int A[2][N], n; vector<int> adj[N];↵
 ↵
void DFS(int v, int p = -1) {↵
    dp[0][v] = dp[1][v] = 0;↵
    for (int u : adj[v]) {↵
        if (u == p) continue;↵
        DFS(u, v);↵
        dp[0][v] += max(abs(A[0][v] - A[1][u]) + dp[1][u], dp[0][u] + abs(A[0][v] - A[0][u]));↵
        dp[1][v] += max(abs(A[1][v] - A[1][u]) + dp[1][u], dp[0][u] + abs(A[1][v] - A[0][u]));↵
    }↵
}↵
 ↵
void Solve() {↵
    scanf("%d", &n);↵
    for (int i = 1; i <= n; i++) scanf("%d%d", &A[0][i], &A[1][i]);↵
    fill(adj + 1, adj + n + 1, vector<int>());↵
    for (int i = 1; i < n; i++) {↵
        int u, v; scanf("%d%d", &u, &v);↵
        adj[u].push_back(v);↵
        adj[v].push_back(u);↵
    }↵
    DFS(1);↵
    printf("%lld\n", max(dp[0][1], dp[1][1]));↵
}↵
 ↵
int main() {↵
    int t; scanf("%d", &t);↵
    while (t--) Solve();↵
    return 0;↵
}↵
~~~~~↵

</spoiler>↵











[problem:1528B]↵

problem idea and solution: [user:alireza_kaviani,2021-05-24]↵

<spoiler summary="editorial">↵
[tutorial:1528B]↵
</spoiler>↵


<spoiler summary="official solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
typedef long long ll;↵
typedef pair<ll, ll> pll;↵
typedef pair<int, int> pii;↵
 ↵
#define X first↵
#define Y second↵
#define endl '\n'↵
 ↵
const int N = 1e6 + 10;↵
const int MOD = 998244353;↵
 ↵
int n, dp[N], S;↵
 ↵
int main() {↵
    ios_base::sync_with_stdio(false); cin.tie(nullptr);↵
    cin >> n;↵
    for (int i = 1; i <= n; i++) {↵
        for (int j = i + i; j <= n; j += i) {↵
            dp[j]++;↵
        }↵
    }↵
    dp[0] = S = 1;↵
    for (int i = 1; i <= n; i++) {↵
        dp[i] = (dp[i] + S) % MOD;↵
        S = (S + dp[i]) % MOD;↵
    }↵
    cout << dp[n] << endl;↵
    return 0;↵
}↵
~~~~~↵

</spoiler>↵







[problem:1528C]↵

problem idea and solution: [user:AliShahali1382,2021-05-24]↵

<spoiler summary="editorial">↵
[tutorial:1528C]↵
</spoiler>↵


<spoiler summary="official solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
 ↵
using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵
 ↵
const int inf=1000000010;↵
const ll INF=1000000000000001000LL;↵
const int mod=1000000007;↵
const int MAXN=300010, LOG=20;↵
 ↵
int n, m, k, u, v, x, y, t, a, b, ans;↵
int par1[MAXN], par2[MAXN];↵
int stt[MAXN], fnt[MAXN], timer;↵
vector<int> G1[MAXN], G2[MAXN];↵
set<pii> st;↵
 ↵
int Add(int v){↵
auto it=st.lower_bound({stt[v], v});↵
if (it!=st.end() && fnt[it->second]<=fnt[v]) return -2;↵
if (it==st.begin()) return -1;↵
--it;↵
int res=it->second;↵
if (fnt[v]>fnt[res]) return -1;↵
st.erase(it);↵
return res;↵
}↵
void dfs1(int node){↵
stt[node]=timer++;↵
for (int v:G2[node]) dfs1(v);↵
fnt[node]=timer;↵
}↵
void dfs2(int node){↵
int res=Add(node);↵
if (res!=-2) st.insert({stt[node], node});↵
ans=max(ans, (int)st.size());↵
for (int v:G1[node]) dfs2(v);↵
if (res!=-2){↵
st.erase({stt[node], node});↵
if (res!=-1) st.insert({stt[res], res});↵
}↵
}↵
 ↵
void Solve(){↵
cin>>n;↵
for (int i=1; i<=n; i++) G1[i].clear(), G2[i].clear();↵
for (int i=2; i<=n; i++) cin>>par1[i], G1[par1[i]].pb(i);↵
for (int i=2; i<=n; i++) cin>>par2[i], G2[par2[i]].pb(i);↵
timer=1;↵
ans=0;↵
dfs1(1);↵
dfs2(1);↵
cout<<ans<<"\n";↵
}↵
 ↵
int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
int T;↵
cin>>T;↵
while (T--) Solve();↵

return 0;↵
}↵
~~~~~↵
</spoiler>↵


<spoiler summary="better implementation of official solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
typedef long long ll;↵
typedef pair<ll, ll> pll;↵
typedef pair<int, int> pii;↵
 ↵
#define X first↵
#define Y second↵
#define endl '\n'↵
 ↵
const int N = 3e5 + 10;↵
 ↵
int t, n, L[N], R[N], timer, now, ans;↵
vector<int> Srsh[N], Msht[N];↵
set<pii> st;↵
 ↵
void MshtDFS(int u) {↵
    L[u] = timer++;↵
    for (int v : Msht[u]) {↵
        MshtDFS(v);↵
    }↵
    R[u] = timer;↵
}↵
 ↵
int ispar(int u, int v) {↵
    return L[u] <= L[v] && R[v] <= R[u];↵
}↵
 ↵
void SrshDFS(int u) {↵
    int last = now;↵
    // add u↵
    auto it = st.lower_bound({L[u], 0});↵
    if (it != st.end())↵
        now += 1 - ispar(u, it->Y);↵
    if (it != st.begin()) {↵
        auto nxt = it--;↵
        now += 1 - ispar(it->Y, u);↵
        if (nxt != st.end())↵
            now -= 1 - ispar(it->Y, nxt->Y);↵
    }↵
    st.insert({L[u], u});↵
    ans = max(ans, now);↵
    // DFS↵
    for (int v : Srsh[u]) {↵
        SrshDFS(v);↵
    }↵
    // remove u↵
    st.erase({L[u], u});↵
    now = last;↵
}↵
 ↵
int main() {↵
    ios_base::sync_with_stdio(false); cin.tie(nullptr);↵
    cin >> t;↵
    while (t --> 0) {↵
        cin >> n;↵
        for (int i = 1; i <= n; i++) {↵
            Srsh[i].clear();↵
            Msht[i].clear();↵
        }↵
        for (int u = 2; u <= n; u++) {↵
            int par; cin >> par;↵
            Srsh[par].push_back(u);↵
        }↵
        for (int u = 2; u <= n; u++) {↵
            int par; cin >> par;↵
            Msht[par].push_back(u);↵
        }↵
        timer = 0;↵
        MshtDFS(1);↵
        ans = now = 0;↵
        SrshDFS(1);↵
        cout << ans + 1 << endl;↵
    }↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵


<spoiler summary="python solution">↵

~~~~~↵
#!/usr/bin/env python↵
import os↵
import sys↵
from io import BytesIO, IOBase↵
 ↵
# region fastio↵
 ↵
BUFSIZE = 8192↵
 ↵
 ↵
class FastIO(IOBase):↵
    newlines = 0↵
 ↵
    def __init__(self, file):↵
        self._fd = file.fileno()↵
        self.buffer = BytesIO()↵
        self.writable = "x" in file.mode or "r" not in file.mode↵
        self.write = self.buffer.write if self.writable else None↵
 ↵
    def read(self):↵
        while True:↵
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))↵
            if not b:↵
                break↵
            ptr = self.buffer.tell()↵
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)↵
        self.newlines = 0↵
        return self.buffer.read()↵
 ↵
    def readline(self):↵
        while self.newlines == 0:↵
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))↵
            self.newlines = b.count(b"\n") + (not b)↵
            ptr = self.buffer.tell()↵
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)↵
        self.newlines -= 1↵
        return self.buffer.readline()↵
 ↵
    def flush(self):↵
        if self.writable:↵
            os.write(self._fd, self.buffer.getvalue())↵
            self.buffer.truncate(0), self.buffer.seek(0)↵
 ↵
 ↵
class IOWrapper(IOBase):↵
    def __init__(self, file):↵
        self.buffer = FastIO(file)↵
        self.flush = self.buffer.flush↵
        self.writable = self.buffer.writable↵
        self.write = lambda s: self.buffer.write(s.encode("ascii"))↵
        self.read = lambda: self.buffer.read().decode("ascii")↵
        self.readline = lambda: self.buffer.readline().decode("ascii")↵
 ↵
 ↵
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)↵
input = lambda: sys.stdin.readline().rstrip("\r\n")↵
    ↵
class FenwickTree:↵
    def __init__(self, x):↵
        """transform list into BIT"""↵
        self.bit = x↵
        for i in range(len(x)):↵
            j = i | (i + 1)↵
            if j < len(x):↵
                x[j] += x[i]↵
    def update(self, idx, x):↵
        """updates bit[idx] += x"""↵
        while idx < len(self.bit):↵
            self.bit[idx] += x↵
            idx |= idx + 1↵
 ↵
    def query(self, end):↵
        """calc sum(bit[:end])"""↵
        end += 1↵
        x = 0↵
        while end:↵
            x += self.bit[end - 1]↵
            end &= end - 1↵
        return x↵
 ↵
    def findkth(self, k):↵
        """Find largest idx such that sum(bit[:idx]) <= k"""↵
        idx = -1↵
        for d in reversed(range(len(self.bit).bit_length())):↵
            right_idx = idx + (1 << d)↵
            if right_idx < len(self.bit) and k >= self.bit[right_idx]:↵
                idx = right_idx↵
                k -= self.bit[idx]↵
        return idx + 1↵
 ↵
g1 = []↵
g2 = []↵
st = []↵
ft = []↵
 ↵
def dfs1(graph, start=0):↵
    n = len(graph)↵
    tim = 1↵
    visited = [False] * n    ↵
    stack = [start]↵
    while stack:↵
        start = stack[-1]↵
        if not visited[start]:↵
            st[start] = tim↵
            tim = tim + 1↵
            visited[start] = True↵
            for child in graph[start]:↵
                if not visited[child]:↵
                    stack.append(child)↵
        else:↵
            stack.pop()↵
            ft[start] = tim↵
 ↵
 ↵
 ↵
def Do(v):↵
    global ans , cnt , mem↵
    fen.update(st[v] , 1);↵
    if(fen.query(ft[v] - 1) - fen.query(st[v])):↵
        mem += [[v , 0 , 0]]↵
        return;↵
    u = fen2.query(st[v]);↵
    ok[v] = 1↵
    cnt += 1↵
    fen2.update(st[v] , v - u)↵
    fen2.update(ft[v] , u - v)↵
    mem += [[v , u , ok[u]]]↵
    cnt -= ok[u]↵
    ok[u] = 0↵
    return;↵
 ↵
 ↵
 ↵
def undo():↵
    global cnt , ans , mem↵
    [v , u , a] = mem[-1]↵
    if(a != 0):↵
        ok[u] = 1↵
        cnt += 1↵
    cnt -= 1↵
    ok[v] = 0↵
    fen.update(st[v] , -1)↵
    fen2.update(st[v] , u - v)↵
    fen2.update(ft[v] , v - u)↵
    mem.pop()↵
    return;↵
 ↵
 ↵
def dfs(graph, start=0):↵
    global ans , cnt↵
    n = len(graph)↵
    visited = [False] * n   ↵
    stack = [start]↵
    while stack:↵
        start = stack[-1]↵
        if not visited[start]:↵
            Do(start)↵
            ans = max(ans , cnt)↵
            visited[start] = True↵
            for child in graph[start]:↵
                if not visited[child]:↵
                    stack.append(child)↵
        else:↵
            stack.pop()↵
            undo()↵
 ↵
 ↵
 ↵
def solve():↵
    global n, g1 , g2 , V , st , ft , fen , fen2 , mem , ok , cnt , ans ↵
    n = int(input())↵
    if(n == 1):↵
        print(1)↵
        exit(0)↵
    ↵
    g1 = [] ; g2 = []↵
    ↵
    for i in range(n):↵
        g1.append([])↵
        g2.append([])↵
    ↵
    # 0 base ↵
    ↵
    V = list(map(int , input().split()))↵
    ↵
    for i in range ( 1 , n ):↵
        v = V[i - 1]-1↵
        g1[v].append(i)↵
    ↵
    V = list(map(int , input().split()))    ↵
    ↵
    for i in range ( 1 , n ):↵
        v = V[i-1]-1↵
        g2[v].append(i)↵
    st = [0] * (n + 100)↵
    ft = [0] * (n + 100)↵
    fen = FenwickTree([0] * (n + 3))↵
    fen2 = FenwickTree([0] * (n + 3))↵
    mem = []↵
    ok = [0]*(n + 100)↵
    cnt = 0↵
    ans = 0↵
    dfs1(g2)↵
    dfs(g1)↵
    print(ans)↵
 ↵
q = int(input())↵
for i in range (q):↵
    solve()↵
~~~~~↵

</spoiler>↵

<spoiler summary="another O(n.log) solution with seg-tree">↵
#include<bits/stdc++.h>↵
#define lc (id * 2)↵
#define rc (id * 2 + 1)↵
#define md ((s + e) / 2)↵
#define dm ((s + e) / 2 + 1)↵
#define ln (e &mdash; s + 1)↵
using namespace std;↵
 ↵
typedef long long ll;↵
const ll MXN = 3e5 + 10;↵
const ll MXS = MXN * 4;↵
ll n, timer, ans, Ans;↵
ll lazy[MXS], seg[MXS];↵
ll Stm[MXN], Ftm[MXN];↵
vector<ll> adj[MXN][2];↵
void Build(ll id = 1, ll s = 1, ll e = n){↵
    lazy[id] = -1, seg[id] = 0;↵
    if(ln > 1) Build(lc, s, md), Build(rc, dm, e);↵
}↵
void Shift(ll id, ll s, ll e){↵
    if(lazy[id] == -1) return;↵
    seg[id] = lazy[id];↵
    if(ln > 1) lazy[lc] = lazy[rc] = lazy[id];↵
    lazy[id] = -1;↵
}↵
void Upd(ll l, ll r, ll x, ll id = 1, ll s = 1, ll e = n){↵
    Shift(id, s, e);↵
    if(e < l || s > r) return;↵
    if(l <= s && e <= r){↵
        lazy[id] = x; Shift(id, s, e);↵
        return;↵
    }↵
    Upd(l, r, x, lc, s, md), Upd(l, r, x, rc, dm, e);↵
    seg[id] = max(seg[lc], seg[rc]);↵
}↵
ll Get(ll l, ll r, ll id = 1, ll s = 1, ll e = n){↵
    Shift(id, s, e);↵
    if(e < l || s > r) return 0;↵
    if(l <= s && e <= r) return seg[id];↵
    return max(Get(l, r, lc, s, md), Get(l, r, rc, dm, e));↵
}↵
void prep(ll u, ll par, ll f){↵
    Stm[u] = ++ timer;↵
    for(auto v : adj[u][f]){↵
        if(v != par) prep(v, u, f);↵
    }↵
    Ftm[u] = timer;↵
}↵
bool Is_Jad(ll j, ll u){↵
    return (Stm[j] <= Stm[u] && Ftm[u] <= Ftm[j]);↵
}↵
void DFS(ll u, ll par, ll f){↵
    ll j = Get(Stm[u], Ftm[u]);↵
    if(!j) Upd(Stm[u], Ftm[u], u), ans ++;↵
    else{↵
        if(Is_Jad(j, u)){↵
            Upd(Stm[j], Ftm[j], 0);↵
            Upd(Stm[u], Ftm[u], u);↵
        }↵
    }↵
    Ans = max(Ans, ans);↵
    for(auto v : adj[u][f]){↵
        if(v != par) DFS(v, u, f);↵
    }↵
    if(!j) Upd(Stm[u], Ftm[u], 0), ans --;↵
    else{↵
        if(Is_Jad(j, u)){↵
            Upd(Stm[u], Ftm[u], 0);↵
            Upd(Stm[j], Ftm[j], j);↵
        }↵
    }↵
}↵
void solve(){↵
    cin >> n, timer = ans = Ans = 0;↵
    for(int i = 1; i <= n; i ++) adj[i][0].clear(), adj[i][1].clear();↵
    for(int t = 0; t < 2; t ++) for(int u = 2, v; u <= n; u ++){↵
        cin >> v, adj[v][t].push_back(u), adj[u][t].push_back(v);↵
    }↵
    Build(), prep(1, 0, 1);↵
    DFS(1, 0, 0);↵
    cout << Ans << '\n';↵
}↵
int main(){↵
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);↵
    ll q; cin >> q;↵
    while(q --) solve();↵
    return 0;↵
}↵
/*!↵
    HE'S AN INSTIGATOR,↵
    ENEMY ELIMINATOR,↵
    AND WHEN HE KNOCKS YOU BETTER↵
    YOU BETTER LET HIM IN.↵
*/↵
//! N.N↵
</spoiler>↵





[problem:1528D]↵

problem idea and solution: [user:AmShZ,2021-05-24], [user:AliShahali1382,2021-05-24]↵

<spoiler summary="editorial">↵
[tutorial:1528D]↵
</spoiler>↵


<spoiler summary="official solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
 ↵
using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵
 ↵
const int inf=1000000010;↵
const ll INF=1000000000000001000LL;↵
const int mod=1000000007;↵
const int N=605;↵
 ↵
int n, m, k, u, v, x, y, t, a, b;↵
bool mark[N];↵
int G[N][N], D[N];↵

inline void upd(int &x, int y){ if (x>y) x=y;}↵

int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
memset(G, 63, sizeof(G));↵
cin>>n>>m;↵
while (m--){↵
cin>>u>>v>>x;↵
G[u][v]=min(G[u][v], x);↵
}↵
for (int i=0; i<n; i++){↵
memset(D, 63, sizeof(D));↵
memset(mark, 0, sizeof(mark));↵
for (int v=0; v<n; v++) upd(D[v], G[i][v]);↵
while (1){↵
int v=-1;↵
for (int x=0; x<n; x++) if (!mark[x]){↵
if (v==-1 || D[v]>D[x]) v=x;↵
}↵
if (v==-1) break ;↵
mark[v]=1;↵
upd(D[(v+1)%n], D[v]+1);↵
for (int u=0; u<n; u++)↵
upd(D[(u+D[v])%n], D[v]+G[v][u]);↵

}↵
for (int j=0; j<n; j++){↵
if (i==j) cout<<"0 ";↵
else cout<<D[j]<<" ";↵
}↵
cout<<"\n";↵
}↵

return 0;↵
}↵
~~~~~↵
</spoiler>↵


<spoiler summary="a different O(n^3) solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
typedef long long ll;↵
 ↵
const int maxn = 600 + 5;↵
 ↵
int n;↵
int dp[maxn];↵
bool mark[maxn];↵
vector<pair<int,int>> g[maxn];↵
int go[maxn];↵
 ↵
int dis(int s, int t) {↵
if (s <= t)↵
return t - s;↵
return n - (s - t);↵
}↵
 ↵
void dijkstra(int src) {↵
memset(dp, 63, sizeof dp);↵
memset(mark, 0, sizeof mark);↵
dp[src] = 0;↵
set<int> S;↵
for (int i = 0; i < n; i++)↵
S.insert(i);↵
for (int i = 0; i < n - 1; i++) {↵
int v = -1;↵
for (int j = 0; j < n; j++) {↵
if (mark[j])↵
continue;↵
if (v == -1 or dp[v] > dp[j])↵
v = j;↵
}↵
S.erase(v);↵
mark[v] = 1;↵
if (v != src) {↵
auto it = S.lower_bound(v);↵
if (it == S.end())↵
it = S.lower_bound(0);↵
int nex = *it;↵
dp[nex] = min(dp[nex], dp[v] + dis(v, nex));↵
}↵
for (int i = 2 * n - 1; i >= 0; i--) {↵
int v = i % n;↵
if (!mark[v])↵
go[v] = v;↵
else↵
go[v] = go[(v + 1) % n];↵
}↵
for (auto [u, w] : g[v]) {↵
int nex = go[(u + dp[v]) % n];↵
dp[nex] = min(dp[nex], dp[v] + w + dis((u + dp[v]) % n, nex));↵
}↵
}↵
}↵
 ↵
int main() {↵
ios_base::sync_with_stdio(false);↵
int m;↵
cin >> n >> m;↵
for (int i = 0; i < m; i++) { ↵
int v, u, w;↵
cin >> v >> u >> w;↵
g[v].push_back({u, w});↵
}↵
for (int i = 0; i < n; i++) {↵
dijkstra(i);↵
for (int j = 0; j < n; j++)↵
cout << dp[j] << " \n"[j == n-1];↵
}↵
}↵
~~~~~↵
</spoiler>↵









[problem:1528E]↵

problem idea and solution: [user:AliShahali1382,2021-05-24]↵

<spoiler summary="editorial">↵
[tutorial:1528E]↵
</spoiler>↵


<spoiler summary="official solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
 ↵
using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵
 ↵
const int inf=1000000010;↵
const ll INF=1000000000000001000LL;↵
const int mod=998244353, inv6=166374059;↵
const int MAXN=1000010, LOG=20;↵
 ↵
ll n, m, k, u, v, x, y, t, a, b, ans;↵
ll dp[MAXN], ps[MAXN];↵
ll pd[MAXN], sp[MAXN];↵
 ↵
ll C3(ll x){↵
return x*(x-1)%mod*(x-2)%mod*inv6%mod;↵
}↵
ll C2(ll x){↵
return x*(x-1)/2%mod;↵
}↵
 ↵
int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
cin>>n;↵
dp[0]=ps[0]=1;↵
pd[0]=sp[0]=1;↵
for (int i=1; i<=n; i++){↵
ps[i]=(1 + ps[i-1] + ps[i-1]*(ps[i-1]+1)/2)%mod;↵
dp[i]=ps[i]-ps[i-1];↵
pd[i]=dp[i]-dp[i-1];↵
sp[i]=(sp[i-1]+pd[i])%mod;↵
}↵
for (int i=0; i<n; i++) ans=(ans + pd[i]*sp[n-1-i])%mod;↵

ans=(ans + 2*C3(ps[n-1]+2))%mod;↵
if (n>=2) ans=(ans - 2*C3(ps[n-2]+2))%mod;↵

ans=(ans + 2*C2(ps[n-1]+1))%mod;↵
if (n>=2) ans=(ans - 2*C2(ps[n-2]+1))%mod;↵

if (ans<0) ans+=mod;↵
cout<<ans<<"\n";↵

return 0;↵
}↵
~~~~~↵

</spoiler>↵









[problem:1528F]↵

problem idea and solution: [user:AmShZ,2021-05-24], [user:AliShahali1382,2021-05-24]↵

<spoiler summary="editorial">↵
[tutorial:1528F]↵
</spoiler>↵


<spoiler summary="official solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
 ↵
using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵
 ↵
const int inf=1000000010;↵
const ll INF=10000000000000010LL;↵
const int mod=998244353;↵
const int MAXN=3000010, LOG=18;↵
 ↵
int n, m, k, u, v, x, y, t, a, b;↵
int rev[MAXN];↵
ll F[MAXN], I[MAXN];↵
ll A[MAXN], B[MAXN], ans;↵
 ↵
ll powmod(ll a, ll b){↵
ll res=1;↵
for (; b; b>>=1, a=a*a%mod) if (b&1) res=res*a%mod;↵
return res;↵
}↵
ll nCr(ll n, ll r){↵
if (r<0 || r>n) return 0;↵
return F[n]*I[r]%mod*I[n-r]%mod;↵
}↵
 ↵
void NTT(ll *A, bool inv){↵
int n=(1<<LOG);↵
for (int i=0; i<(1<<LOG); i++) if (rev[i]<i) swap(A[i], A[rev[i]]);↵
for (int ln=1; ln<n; ln<<=1){↵
ll w=powmod(3, mod/2/ln);↵
if (inv) w=powmod(w, mod-2);↵
for (int i=0; i<n; i+=2*ln){↵
ll wn=1;↵
for (int j=i; j<i+ln; j++){↵
ll x=A[j], y=A[j+ln]*wn;↵
A[j]=(x+y)%mod;↵
A[j+ln]=(x-y)%mod;↵
wn=wn*w%mod;↵
}↵
}↵
}↵
if (inv){↵
ll invn=powmod(1<<LOG, mod-2);↵
for (int i=0; i<n; i++) A[i]=A[i]*invn%mod;↵
}↵
}↵
 ↵
int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
F[0]=1;↵
for (int i=1; i<MAXN; i++) F[i]=F[i-1]*i%mod;↵
I[MAXN-1]=powmod(F[MAXN-1], mod-2);↵
for (int i=MAXN-1; i; i--) I[i-1]=I[i]*i%mod;↵
for (int i=1; i<(1<<LOG); i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(LOG-1));↵

cin>>n>>k;↵
for (int i=0; i<=k; i++){↵
A[i]=powmod(i, k)*I[i]%mod;↵
B[i]=I[i];↵
if (i&1) B[i]*=-1;↵
}↵
NTT(A, 0);↵
NTT(B, 0);↵
for (int i=0; i<MAXN; i++) A[i]=A[i]*B[i]%mod;↵
NTT(A, 1);↵
ll mul=1;↵
for (int i=0; i<=min(n, k); i++){↵
ll val=mul*powmod(n+1, n-i)%mod;↵
ans=(ans + val*A[i])%mod;↵
mul=mul*(n-i)%mod;↵
}↵
if (ans<0) ans+=mod;↵
cout<<ans<<"\n";↵

return 0;↵
}↵
~~~~~↵
</spoiler>↵





History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en30 English Tet 2021-05-25 19:13:31 65
en29 English Tet 2021-05-24 23:28:33 2659
en28 English Tet 2021-05-24 23:24:56 0 Tiny change: 'orial:1528F]\n</spoil' -> 'orial:1528A]\n</spoil'
en27 English Tet 2021-05-24 22:17:38 4 Tiny change: ' solution[Atreus]">\' -> ' solution[user:Atreus]">\'
en26 English Tet 2021-05-24 22:15:57 5 Tiny change: 'Hello, Codeforc' -> 'Hi, Codeforc'
en25 English Tet 2021-05-24 22:15:21 0 (published)
en24 English Dio 2021-05-24 22:12:35 12 (saved to drafts)
en23 English AliShahali1382 2021-05-24 22:02:31 41
en22 English AliShahali1382 2021-05-24 21:58:48 32
en21 English AliShahali1382 2021-05-24 21:51:32 14
en20 English AliShahali1382 2021-05-24 21:40:17 2 Tiny change: 'orces!\n\n[probl' -> 'orces!\n\n\n[probl' (published)
en19 English AliShahali1382 2021-05-24 21:37:45 16 Tiny change: 'm:1529A]\nproblem ' -> 'm:1529A]\n\nproblem '
en18 English AliShahali1382 2021-05-24 21:36:47 800
en17 English AliShahali1382 2021-05-24 21:33:16 268
en16 English AliShahali1382 2021-05-24 21:31:39 109
en15 English AliShahali1382 2021-05-24 21:29:30 38 Tiny change: 'spoiler>\n\nproblem ' -> 'spoiler>\nproblem '
en14 English AliShahali1382 2021-05-24 21:11:20 1634
en13 English AliShahali1382 2021-05-24 21:07:02 1627
en12 English Dio 2021-05-24 21:03:31 160
en11 English Dio 2021-05-24 21:02:25 2 Tiny change: '\n~~~~~\n/ Call my ' -> '\n~~~~~\n// Call my '
en10 English Dio 2021-05-24 21:01:43 1 Tiny change: 'spoiler>\n\nproblem ' -> 'spoiler>\nproblem '
en9 English AliShahali1382 2021-05-24 20:59:59 8
en8 English AliShahali1382 2021-05-24 20:58:23 2
en7 English AliShahali1382 2021-05-24 20:57:19 7357
en6 English AliShahali1382 2021-05-24 20:42:46 14185
en5 English AliShahali1382 2021-05-24 20:23:44 10
en4 English AliShahali1382 2021-05-24 20:22:34 47
en3 English AliShahali1382 2021-05-24 20:21:37 1939
en2 English AliShahali1382 2021-05-24 20:17:44 89
en1 English AliShahali1382 2021-05-24 20:09:46 32 Initial revision (saved to drafts)