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