C++转C，转挂了求助
- 板块SP375 QTREE - Query on a tree
- 楼主Vitamin_B
- 当前回复0
- 已保存回复0
- 发布时间2024/9/26 19:19
- 上次更新2024/9/26 21:15:58
查看原帖
被骇客银狼阻止的越权访问保存失败
C++转C，转挂了求助
AC的c++代码：
# include <bits/stdc++.h>
//# include <windows.h>
# define I return
# define AK 0
# define IOI ;
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
struct node {
int x, w, id;
} ;
int t, n, s[10005], heavist[10005], x, y, tot, dfn[10005], a[10005], b[10005], tr[40005], k, st[10005], depth[10005], f[10005], mp[10005];
string op;
vector <node> v[10005];
void init1 (const int x, const int fa) {
s[x] = 1, f[x] = fa, heavist[x] = 0;
depth[x] = depth[fa] + 1;
for (const node& i : v[x])
if (i.x != fa) {
b[i.x] = i.w, mp[i.id] = i.x;
init1 (i.x, x);
s[x] += s[i.x];
if (s[heavist[x]] < s[i.x])
heavist[x] = i.x;
}
return ;
}
void init2 (const int x, const int fa, const int s) {
a[dfn[x] = ++ tot] = b[x], st[x] = s;
// cerr << x << ':' << dfn[x] << ',' << a[x] << ',' << st[x] << ',' << depth[x] << ',' << ::s[x] << ',' << heavist[x] << '\n';
if (! heavist[x])
return ;
init2 (heavist[x], x, s);
for (const node& i : v[x])
if (i.x != fa && i.x != heavist[x])
init2 (i.x, x, i.x);
return ;
}
void build (const int x, const int l, const int r) {
if (l == r) {
tr[x] = a[l];
// cerr << x << ',' << l << ':' << dfn[l] << '&' << tr[x] << '\n';
return ;
}
const int mid = l + r >> 1, left = x << 1, right = left | 1;
build (left, l, mid), build (right, mid + 1, r);
tr[x] = max (tr[left], tr[right]);
// cerr << x << ',' << l << '~' << r << ':' << tr[x] << '\n';
return ;
}
void change (const int x, const int l, const int r, const int t) {
if (l == r) {
tr[x] = k;
// cerr << x << ',' << l << ':' << tr[x] << '\n';
return ;
}
const int mid = l + r >> 1, left = x << 1, right = left | 1;
if (t <= mid)
change (left, l, mid, t);
else
change (right, mid + 1, r, t);
tr[x] = max (tr[left], tr[right]);
// cerr << x << ',' << l << '~' << r << ':' << tr[x] << '\n';
return ;
}
int find (const int x, const int l, const int r, const int L, const int R) {
// cerr << x << ',' << l << '~' << r << ':' << tr[x] << '\n';
if (l == L && r == R)
return tr[x];
const int mid = l + r >> 1, left = x << 1, right = left | 1;
if (R <= mid)
return find (left, l, mid, L, R);
if (L > mid)
return find (right, mid + 1, r, L, R);
return max (find (left, l, mid, L, mid), find (right, mid + 1, r, mid + 1, R));
}
int find_path (int x, int y) {
int maxx = 0;
while (st[x] != st[y]) {
if (depth[st[x]] < depth[st[y]])
swap (x, y);
maxx = max (maxx, find (1, 1, n, dfn[st[x]], dfn[x]));
// cerr << st[x] << '~' << x << ':' << maxx << '\n';
x = f[st[x]];
}
if (dfn[x] > dfn[y])
swap (x, y);
if (dfn[x] < dfn[y])
maxx = max (maxx, find (1, 1, n, dfn[x] + 1, dfn[y]));
// cerr << dfn[x] + 1 << '~' << dfn[y] << ':' << maxx << '\n';
return maxx;
}
void change_edge (const int x) {
// cerr << mp[x] << ',' << dfn[mp[x]] << "->" << k << '\n';
change (1, 1, n, dfn[mp[x]]);
return ;
}
int main () {
ios::sync_with_stdio (0);
cin.tie (0);
cout.tie (0);
cin >> t;
while (t --) {
cin >> n, tot = 0;
for (int i = 1; i <= n; ++ i)
v[i].clear ();
for (int i = 1; i < n; ++ i)
cin >> x >> y >> k, v[x].push_back ({y, k, i}), v[y].push_back ({x, k, i});
init1 (1, 0), init2 (1, 0, 1), build (1, 1, n);
while (cin >> op, op[0] != 'D') {
cin >> x >> k;
if (op[0] == 'C')
change_edge (x);
else
cout << find_path (x, k) << '\n';
// # include <windows.h>
// Sleep (1000);
// system ("pause");
}
}
I AK IOI
}
/*
10
1 2 2
1 4 3
1 5 8
2 3 5
2 6 10
4 7 9
6 9 6
7 8 9
7 10 2
CHANGE 7 8
CHANGE 3 5
QUERY 3 9
DONE
*/
C（样例MLE）:
# include <stdio.h>
# define I return
# define AK 0
# define IOI ;
typedef long long ll;
struct node {
int x, w, id;
} edge[20005];
int e, head[10005], nxt[20005], t, n, s[10005], heavist[10005], x, y, tot, dfn[10005], a[10005], b[10005], tr[40005], k, st[10005], depth[10005], f[10005], mp[10005];
char op[10];
int max (const int x, const int y) {
return x > y ? x : y;
}
void add (const int x, const int y, const int w, const int id) {
edge[++ tot].x = y, edge[tot].w = w, edge[tot].id = id;
nxt[tot] = head[x];
head[x] = tot;
return ;
}
void init1 (const int x, const int fa) {
s[x] = 1, f[x] = fa, heavist[x] = 0;
depth[x] = depth[fa] + 1;
for (int i = head[x]; i; i = nxt[i])
if (edge[i].x != fa) {
b[edge[i].x] = edge[i].w, mp[edge[i].id] = edge[i].x;
init1 (edge[i].x, x);
s[x] += s[edge[i].x];
if (s[heavist[x]] < s[edge[i].x])
heavist[x] = edge[i].x;
}
return ;
}
void init2 (const int x, const int fa, const int s) {
a[dfn[x] = ++ tot] = b[x], st[x] = s;
// cerr << x << ':' << dfn[x] << ',' << a[x] << ',' << st[x] << ',' << depth[x] << ',' << ::s[x] << ',' << heavist[x] << '\n';
if (! heavist[x])
return ;
init2 (heavist[x], x, s);
for (int i = head[x]; i; i = nxt[i])
if (edge[i].x != fa && edge[i].x != heavist[x])
init2 (edge[i].x, x, edge[i].x);
return ;
}
void build (const int x, const int l, const int r) {
if (l == r) {
tr[x] = a[l];
// cerr << x << ',' << l << ':' << dfn[l] << '&' << tr[x] << '\n';
return ;
}
const int mid = l + r >> 1, left = x << 1, right = left | 1;
build (left, l, mid), build (right, mid + 1, r);
tr[x] = max (tr[left], tr[right]);
// cerr << x << ',' << l << '~' << r << ':' << tr[x] << '\n';
return ;
}
void change (const int x, const int l, const int r, const int t) {
if (l == r) {
tr[x] = k;
// cerr << x << ',' << l << ':' << tr[x] << '\n';
return ;
}
const int mid = l + r >> 1, left = x << 1, right = left | 1;
if (t <= mid)
change (left, l, mid, t);
else
change (right, mid + 1, r, t);
tr[x] = max (tr[left], tr[right]);
// cerr << x << ',' << l << '~' << r << ':' << tr[x] << '\n';
return ;
}
int find (const int x, const int l, const int r, const int L, const int R) {
// cerr << x << ',' << l << '~' << r << ':' << tr[x] << '\n';
if (l == L && r == R)
return tr[x];
const int mid = l + r >> 1, left = x << 1, right = left | 1;
if (R <= mid)
return find (left, l, mid, L, R);
if (L > mid)
return find (right, mid + 1, r, L, R);
return max (find (left, l, mid, L, mid), find (right, mid + 1, r, mid + 1, R));
}
int find_path (int x, int y) {
int maxx = 0;
while (st[x] != st[y]) {
if (depth[st[x]] < depth[st[y]])
x ^= y, y ^= x, x ^= y;
maxx = max (maxx, find (1, 1, n, dfn[st[x]], dfn[x]));
// cerr << st[x] << '~' << x << ':' << maxx << '\n';
x = f[st[x]];
}
if (dfn[x] > dfn[y])
x ^= y, y ^= x, x ^= y;
if (dfn[x] < dfn[y])
maxx = max (maxx, find (1, 1, n, dfn[x] + 1, dfn[y]));
// cerr << dfn[x] + 1 << '~' << dfn[y] << ':' << maxx << '\n';
return maxx;
}
void change_edge (const int x) {
// cerr << mp[x] << ',' << dfn[mp[x]] << "->" << k << '\n';
change (1, 1, n, dfn[mp[x]]);
return ;
}
int main () {
scanf ("%d", &t);
while (t --) {
scanf ("%d", &n), e = tot = 0;
for (int i = 1; i <= n; ++ i)
head[i] = 0;
for (int i = 1; i < n; ++ i)
scanf ("%d%d%d", &x, &y, &k), add (x, y, k, i), add (y, x, k, i);
init1 (1, 0), init2 (1, 0, 1), build (1, 1, n);
while (scanf ("%s", op), op[0] != 'D') {
scanf ("%d%d", &x, &k);
if (op[0] == 'C')
change_edge (x);
else
printf ("%d\n", find_path (x, k));
// # include <windows.h>
// Sleep (1000);
// system ("pause");
}
}
I AK IOI
}
/*
10
1 2 2
1 4 3
1 5 8
2 3 5
2 6 10
4 7 9
6 9 6
7 8 9
7 10 2
CHANGE 7 8
CHANGE 3 5
QUERY 3 9
DONE
*/
加载中...