I tried to modify my code. But it still returned WA on test #25.
This is the statement and the code: https://codeforces.net/problemset/submission/464/185632015
Thanks a lot!
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 150 |
I tried to modify my code. But it still returned WA on test #25.
This is the statement and the code: https://codeforces.net/problemset/submission/464/185632015
Thanks a lot!
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10, MOD = 1e9 + 7;
int head[N], ed[M], nxt[M], w[M], root[N];
int idx, tot, n, m, _, Start, End;
unsigned long long k[N];
struct SegmentTree
{
int lc, rc, val;
unsigned long long h, size;
}tree[N << 7];
struct Heap
{
int rt, s;
};
int query(int p, int l, int r, int loc)
{
if (l == r) return p;
int mid = l + r >> 1;
if (loc <= mid) return query(tree[p].lc, l, mid, loc);
else return query(tree[p].rc, mid + 1, r, loc);
}
int cmp(int p, int q, int l, int r)
{
//cout << l << ' ' << r << ' ' << tree[p].h << ' ' << tree[q].h << ' ' << tree[p].val << ' ' << tree[q].val << endl;
if (l == r || tree[p].h == tree[q].h) return tree[p].val > tree[q].val;
int mid = l + r >> 1;
if (tree[tree[p].rc].h != tree[tree[q].rc].h) return cmp(tree[p].rc, tree[q].rc, mid + 1, r);
return cmp(tree[p].lc, tree[q].lc, l, mid);
}
bool operator <(const Heap a, const Heap b)
{
return cmp(root[a.rt], root[b.rt], 1, N - 5);
}
inline void update(int p, int l, int mid)
{
tree[p].h = tree[tree[p].lc].h * k[mid - l + 1] + tree[tree[p].rc].h;
tree[p].size = tree[tree[p].lc].size + tree[tree[p].rc].size;
}
inline void add(int a, int b, int c)
{
ed[idx] = b, w[idx] = c, nxt[idx] = head[a], head[a] = idx ++;
}
int build(int l = 1, int r = N - 5)
{
int p = ++ tot;//cout << l << ' ' << r << ' ' << p << endl;
if (l == r) { tree[p].val = tree[p].h = tree[p].size = 0;
//cout << tree[p].val << endl;
return p;}
int mid = l + r >> 1;
tree[p].lc = build(l, mid);
tree[p].rc = build(mid + 1, r);
update(p, l, mid);
return p;
}
inline int find(int p, int x)
{
int z = tree[p].rc, lz = (N - 4 >> 1) + 1, rz = N - 5;
int l = 1, r = N - 5;
while (l < r)
{
int mid = l + r >> 1;
if (x <= mid)
{
if (tree[tree[p].rc].size != r - mid) z = tree[p].rc, lz = mid + 1, rz = r;
//cout << lz << ' ' << rz << ' ' << tree[tree[p].rc].size << endl;
r = mid;
p = tree[p].lc;
}
else l = mid + 1, p = tree[p].rc;
}
//cout << lz << ' ' << rz << endl;
while (lz < rz)
{
//cout << lz << ' ' << rz << endl;
int mid = lz + rz >> 1;
if (tree[tree[z].lc].size != mid - lz + 1) z = tree[z].lc, rz = mid;//, cout << 111 << endl;
else if (tree[tree[z].rc].size != rz - mid) z = tree[z].rc, lz = mid + 1;//, cout << 222 << endl;
else return rz;
}
//puts("");
return lz - 1;
}
int cover(int now, int q, int l, int r, int ql, int qr)
{
//cout << l << ' ' << r << ' ' << ql << ' ' << qr << endl;
int p = 0;
if (now != root[0]) p = ++ tot;
else p = root[_];
tree[p] = tree[q];
if (ql <= l && r <= qr) { tree[p] = tree[now]; return p;}
int mid = l + r >> 1;
if (ql <= mid) tree[p].lc = cover(tree[now].lc, tree[q].lc, l, mid, ql, qr);
if (qr > mid) tree[p].rc = cover(tree[now].rc, tree[q].rc, mid + 1, r, ql, qr);
update(p, l, mid);
return p;
}
int insert(int now, int l, int r, int loc, int x)
{
int p = ++ tot;//cout << l << ' ' << r << ' ' << p << endl;
tree[p] = tree[now];
if (l == r) { tree[p].val = x, tree[p].size = x, tree[p].h = x; return p;}
int mid = l + r >> 1;
if (loc <= mid) tree[p].lc = insert(tree[now].lc, l, mid, loc, x);
else tree[p].rc = insert(tree[now].rc, mid + 1, r, loc, x);
update(p, l, mid);
return p;
}
void add(int rt, int x)
{
int t = query(rt, 1, N - 5, x);
if (tree[t].val == 0)
root[++_] = insert(rt, 1, N - 5, x, 1);
else
{
//cout << 11111111111 << endl;
int u = find(rt, x);
//cout << u << endl;
//for (int j = 1; j <= N - 5; ++j)
//cout << tree[query(root[rt], 1, N - 5, j)].val << ' ';
//puts("");
root[++_] = insert(rt, 1, N - 5, u + 1, 1);
cover(root[0], root[_], 1, N - 5, x, u);
//for (int j = 1; j <= N - 5; ++j)
//cout << tree[query(root[_], 1, N - 5, j)].val << ' ';
//puts("");
}
}
inline int read()
{
register int s = 0, w = 1;
register char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
inline int power(int x)
{
int res = 1, a = 2;
for (; x; x >>= 1)
{
if (x & 1) res = res * a % MOD;
a = a * a % MOD;
}
return res;
}
void dijkstra()
{
bool v[N];
int sw[N], st[N], endrt = -1;
memset(v, 0, sizeof v);
memset(sw, -1, sizeof sw);
priority_queue<Heap> heap;
stack<int> sta;
heap.push({0, Start});
while (!heap.empty())
{
//for (int i = 1; i <= 4; ++i) cout << v[i] << ' '; puts("");
Heap t = heap.top();
heap.pop();
int u = t.s;
if (v[u]) continue;
v[u] = true;
if (u == End)
{
endrt = t.rt;
break;
}
for (int i = head[u]; ~i; i = nxt[i])
{
//for (int j = 1; j <= N - 5; ++j)
//cout << tree[query(root[t.rt], 1, N - 5, j)].val << ' ';
//puts("");
//cout << w[i] + 1 << endl;
//cout << tree[query(root[t.rt], 1, N - 5, w[i] + 1)].val << endl;
add(root[t.rt], w[i] + 1);
//for (int j = 1; j <= N - 5; ++j)
//cout << tree[query(root[_], 1, N - 5, j)].val << ' ';
//puts("");
//cout << u << endl;
//puts("");
if (!v[ed[i]] && (sw[ed[i]] == -1 || cmp(root[sw[ed[i]]], root[_], 1, N - 5)))
{
sw[ed[i]] = _, st[ed[i]] = u;
heap.push({sw[ed[i]], ed[i]});
}
//cout << u << ' ' << sw[u] << ' ' << ed[i] << ' ' << sw[ed[i]] << endl;
//for (int j = 1; j <= N - 5; ++j)
//cout << tree[query(root[sw[u]], 1, N - 5, j)].val << endl;
}
}
if (endrt == -1)
{
puts("-1");
return;
}
//cout << endrt << endl;
int ans = 0;
for (int i = 1; i <= 120 - 5; ++i)
ans = (ans + (tree[query(root[endrt], 1, N - 5, i)].val ? power(i - 1) : 0)) % MOD;//, cout << i << ' ' << ans << endl;
//for (int i = 1; i <= N - 5; ++i)
//cout << tree[query(root[endrt], 1, N - 5, i)].val << endl;
printf("%lld\n", ans);
int cnt = 1, tmp = End;
while (tmp != Start) sta.push(tmp), tmp = st[tmp], ++ cnt;
printf("%lld\n", cnt);
printf("%lld ", Start);
while (!sta.empty())
{printf("%lld ", sta.top()); sta.pop();}
}
signed main()
{
//freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
k[0] = 1;
for (int i = 1; i <= N - 5; ++i)
k[i] = k[i - 1] * 131;
memset(head, -1, sizeof head);
//cout << 11111 << endl;
n = read(), m = read();
for (int i = 1; i <= m; ++i)
{
int x = read(), y = read(), z = read();
add(x, y, z); add(y, x, z);
}
Start = read(), End = read();
//cout << Start << ' ' << End << endl;
//cout << 2222 << endl;
root[0] = build();
//cout << 3333 << endl;
//for (int i = 1; i <= 2; ++i) ++_, root[_] = insert(root[_ - 1], 1, N - 5, i, 1);
//cout << ((Heap){_, 1} < (Heap){_ - 5, 10}) << endl;
//add(root[_], 1);
/*n = read();
for (int i = 1; i <= n; ++i)
{
int x = read();
++ _;
root[_] = insert(root[_ - 1], 1, N - 5, i, x);
}
int rt1 = _;
for (int i = 1; i <= n; ++i)
{
int x = read();
++ _;
root[_] = insert(root[_ - 1], 1, N - 5, i, x);
}
int rt2 = _;*/
//for (int i = 1; i <= 20; ++i) cout << tree[query(root[rt2], 1, N - 5, i)].val << ' ' << tree[query(root[rt2], 1, N - 5, i)].h << endl;
//cout << tree[root[rt1]].h << ' ' << tree[root[rt2]].h << endl;
/*if (cmp(root[rt1], root[rt2], 1, N - 5)) printf("a bigger");
else if (cmp(root[rt2], root[rt1], 1, N - 5)) printf("b bigger");
else printf("equal");*/
//for (int i = 1; i <= 10; ++i) cout << tree[query(root[_], 1, N - 5, i)].val << ' ' << query(root[_], 1, N - 5, i) << endl;
dijkstra();
//cout << 4444 << endl;
return 0;
}
This submission returned WA on point #10, but I don't know where is wrong.
Help! Thank u very much.
Name |
---|