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 = — 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 — 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>↵
↵
↵
↵
↵
↵
↵
↵
[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 = — 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 — 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>↵
↵
↵
↵
↵
↵
