QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #253065 | #5313. Please Save Pigeland | KULIANLEN | Compile Error | / | / | C++14 | 6.1kb | 2023-11-16 17:15:31 | 2023-11-16 17:15:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 5e5 + 5,INF = 1e18;
#define ls (u << 1)
#define rs (u << 1 | 1)
#define sum(u) (tr[u].sum)
#define d(u) (tr[u].d)
#define tot(u) (tr[u].tot)
struct node{
int l,r;
int sum,d;
int tot;
}tr[N << 2];
int a[N],b[N];
void pushup(int u)
{
sum(u) = sum(ls) + sum(rs);tot(u) = tot(ls) + tot(rs);
d(u) = __gcd(d(ls), d(rs));
}
void build(int u,int l,int r)
{
if(l == r)tr[u] = {l, l, a[l], a[l], b[l]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
}
void upd(int u,int x,int d)
{
if(tr[u].l == tr[u].r)
{
sum(u) = x;
d(u) = x;tot(u) = x;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid)upd(ls, x, d);
else upd(rs, x, d);
pushup(u);
}
}
node que(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u];
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
node res = {0,0,0,0};
if(l <= mid)
{
res = que(ls, l, r);
}
if(r > mid)
{
node tmp = que(rs ,l ,r);
res.sum += tmp.sum;
res.d = __gcd(res.d, tmp.d);
}
return res;
}
}
int quesum(int l,int r)
{
return que(1, l, r).sum;
}
int quegcd(int l,int r)
{
int sum = 0;
sum = que(1, 1, l).sum;
int d = 0;
if(l != r)
d = que(1, l + 1, r).d;
return abs(__gcd(sum, d));
}
bool st[N];vector<pair<int,int>> g[N];
int cnt,dfsn[N],rdfsn[N],n,k;
void dfs(int u,int f,int d)
{
dfsn[u] = INF;
if(st[u])dfsn[u] = ++cnt,rdfsn[u] = cnt,b[dfsn[u]] = d;
for(auto t : g[u])
{
int to = t.first,val = t.second;
if(to == f)continue;
dfs(to, u, d + val);
dfsn[u] = min(dfsn[u], dfsn[to]);
rdfsn[u] = max(rdfsn[to], rdfsn[u]);
}
}
void upd1(int l,int r,int x)
{
if(l < 1 || r > k || l > r)return;
upd(1, l, x);
if(r + 1 <= k)upd(1, r + 1, -x);
}
int ans = 1e18;
void dfs1(int u,int f)
{
int res = quegcd(1,k);
int dis = tr[1].tot;
ans = min(ans, dis / res);
for(auto t : g[u])
{
int to = t.first,val = t.second;
if(to == f)continue;
int l = dfsn[to],r = rdfsn[to];
if(l <= r)
{
upd1(l, r, -val);
upd1(1, l, val);
upd1(r + 1, k, val);
dfs1(to, u);
upd1(l, r, val);
upd1(1, l, -val);
upd1(r + 1, k, -val);
}
else
{
upd1(1, k, val);
dfs1(to, u);
upd1(1, k, -val);
}
}
}
signed main()
{
cin >> n >> k;
for(int i = 1;i <= k;i++)
{
int t;cin >> t;st[t] = true;
}
for(int i = 1;i < n;i++)
{
int u,v,w;cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs(1,0,0);
for(int i = 1;i <= k;i++)a[i] = b[i] - b[i - 1];
build(1,1,k);
dfs1(1,0);
cout << ans * 2 << endl;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 5e5 + 5,INF = 1e18;
#define ls (u << 1)
#define rs (u << 1 | 1)
#define sum(u) (tr[u].sum)
#define d(u) (tr[u].d)
#define tot(u) (tr[u].tot)
#define mk(u) (tr[u].mk)
struct node{
int l,r;
int sum,d;
int tot,mk;
}tr[N << 2];
int a[N],b[N];
void pushup(int u)
{
sum(u) = sum(ls) + sum(rs);tot(u) = tot(ls) + tot(rs);
d(u) = __gcd(d(ls), d(rs));
}
void pushdown(int u)
{
tot(ls) += mk(u) * (tr[ls].r - tr[ls].l + 1);
tot(rs) += mk(u) * (tr[rs].r - tr[rs].l + 1);
mk(ls) += mk(u);mk(rs) += mk(u);
mk(u) = 0;
}
void build(int u,int l,int r)
{
if(l == r)tr[u] = {l, l, a[l], a[l], b[l]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
}
void upd2(int u,int l,int r,int d)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tot(u) += d * (tr[u].r - tr[u].l + 1);
mk(u) += d;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid)upd2(ls, l, r, d);
if(r > mid)upd2(rs, l, r, d);
pushup(u);
}
}
void upd(int u,int x,int d)
{
if(tr[u].l == tr[u].r)
{
sum(u) = x;
d(u) = x;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid)upd(ls, x, d);
else upd(rs, x, d);
pushup(u);
}
}
node que(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u];
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
node res = {0,0,0,0,0,0};
if(l <= mid)
{
res = que(ls, l, r);
}
if(r > mid)
{
node tmp = que(rs ,l ,r);
res.sum += tmp.sum;
res.d = __gcd(res.d, tmp.d);
res.tot += tmp.tot;
}
return res;
}
}
int quesum(int l,int r)
{
return que(1, l, r).sum;
}
int quegcd(int l,int r)
{
int sum = 0;
sum = que(1, 1, l).sum;
int d = 0;
if(l != r)
d = que(1, l + 1, r).d;
return abs(__gcd(sum, d));
}
bool st[N];vector<pair<int,int>> g[N];
int cnt,dfsn[N],rdfsn[N],n,k;
void dfs(int u,int f,int d)
{
dfsn[u] = INF;
if(st[u])dfsn[u] = ++cnt,rdfsn[u] = cnt,b[dfsn[u]] = d;
for(auto t : g[u])
{
int to = t.first,val = t.second;
if(to == f)continue;
dfs(to, u, d + val);
dfsn[u] = min(dfsn[u], dfsn[to]);
rdfsn[u] = max(rdfsn[to], rdfsn[u]);
}
}
void upd1(int l,int r,int x)
{
if(l < 1 || r > k || l > r)return;
upd(1, l, x);
upd2(1, l, r, x);
if(r + 1 <= k)upd(1, r + 1, -x),upd2(1, r + 1, k, -x);
}
int ans = 1e18;
void dfs1(int u,int f)
{
int res = quegcd(1,k);
int dis = tr[1].tot;
// cout << res <<" " << dis << endl;
ans = min(ans, dis / res);
for(auto t : g[u])
{
int to = t.first,val = t.second;
if(to == f)continue;
int l = dfsn[to],r = rdfsn[to];
if(l <= r)
{
upd1(l, r, -val);
upd1(1, l, val);
upd1(r + 1, k, val);
dfs1(to, u);
upd1(l, r, val);
upd1(1, l, -val);
upd1(r + 1, k, -val);
}
else
{
upd1(1, k, val);
dfs1(to, u);
upd1(1, k, -val);
}
}
}
signed main()
{
cin >> n >> k;
for(int i = 1;i <= k;i++)
{
int t;cin >> t;st[t] = true;
}
for(int i = 1;i < n;i++)
{
int u,v,w;cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs(1,0,0);
for(int i = 1;i <= k;i++)a[i] = b[i] - b[i - 1];
build(1,1,k);
dfs1(1,0);
cout << ans * 2 << endl;
}
Details
answer.code:179:11: error: redefinition of ‘const long long int N’
179 | const int N = 5e5 + 5,INF = 1e18;
| ^
answer.code:5:11: note: ‘const long long int N’ previously defined here
5 | const int N = 5e5 + 5,INF = 1e18;
| ^
answer.code:179:23: error: redefinition of ‘const long long int INF’
179 | const int N = 5e5 + 5,INF = 1e18;
| ^~~
answer.code:5:23: note: ‘const long long int INF’ previously defined here
5 | const int N = 5e5 + 5,INF = 1e18;
| ^~~
answer.code:186:8: error: redefinition of ‘struct node’
186 | struct node{
| ^~~~
answer.code:11:8: note: previous definition of ‘struct node’
11 | struct node{
| ^~~~
answer.code:190:2: error: conflicting declaration ‘int tr [2000020]’
190 | }tr[N << 2];
| ^~
answer.code:15:2: note: previous declaration as ‘node tr [2000020]’
15 | }tr[N << 2];
| ^~
answer.code:191:5: error: redefinition of ‘long long int a [500005]’
191 | int a[N],b[N];
| ^
answer.code:16:5: note: ‘long long int a [500005]’ previously declared here
16 | int a[N],b[N];
| ^
answer.code:191:10: error: redefinition of ‘long long int b [500005]’
191 | int a[N],b[N];
| ^
answer.code:16:10: note: ‘long long int b [500005]’ previously declared here
16 | int a[N],b[N];
| ^
answer.code:193:6: error: redefinition of ‘void pushup(long long int)’
193 | void pushup(int u)
| ^~~~~~
answer.code:18:6: note: ‘void pushup(long long int)’ previously defined here
18 | void pushup(int u)
| ^~~~~~
answer.code: In function ‘void pushdown(long long int)’:
answer.code:185:22: error: ‘struct node’ has no member named ‘mk’
185 | #define mk(u) (tr[u].mk)
| ^~
answer.code:200:20: note: in expansion of macro ‘mk’
200 | tot(ls) += mk(u) * (tr[ls].r - tr[ls].l + 1);
| ^~
answer.code:185:22: error: ‘struct node’ has no member named ‘mk’
185 | #define mk(u) (tr[u].mk)
| ^~
answer.code:201:20: note: in expansion of macro ‘mk’
201 | tot(rs) += mk(u) * (tr[rs].r - tr[rs].l + 1);
| ^~
answer.code:185:22: error: ‘struct node’ has no member named ‘mk’
185 | #define mk(u) (tr[u].mk)
| ^~
answer.code:202:9: note: in expansion of macro ‘mk’
202 | mk(ls) += mk(u);mk(rs) += mk(u);
| ^~
answer.code:185:22: error: ‘struct node’ has no member named ‘mk’
185 | #define mk(u) (tr[u].mk)
| ^~
answer.code:202:19: note: in expansion of macro ‘mk’
202 | mk(ls) += mk(u);mk(rs) += mk(u);
| ^~
answer.code:185:22: error: ‘struct node’ has no member named ‘mk’
185 | #define mk(u) (tr[u].mk)
| ^~
answer.code:202:25: note: in expansion of macro ‘mk’
202 | mk(ls) += mk(u);mk(rs) += mk(u);
| ^~
answer.code:185:22: error: ‘struct node’ has no member named ‘mk’
185 | #define mk(u) (tr[u].mk)
| ^~
answer.code:202:35: note: in expansion of macro ‘mk’
202 | mk(ls) += mk(u);mk(rs) += mk(u);
| ^~
answer.code:185:22: error: ‘struct node’ has no member named ‘mk’
185 | #define mk(u) (tr[u].mk)
| ^~
answer.code:203:9: note: in expansion of macro ‘mk’
203 | mk(u) = 0;
| ^~
answer.code: At global scope:
answer.code:206:6: error: redefinition of ‘void build(long long int, long long int, long long int)’
206 | void build(int u,int l,int r)
| ^~~~~
answer.code:24:6: note: ‘void build(long long int, long long int, long long int)’ previously defined here
24 | void build(int u,int l,int r)
| ^~~~~
answer.code: In function ‘void upd2(long long int, long long int, long long int, long long int)’:
answer.code:185:22: error: ‘struct node’ has no member named ‘mk’
185 | #define mk(u) (tr[u].mk)
| ^~
answer.code:224:17: note: in expansion of macro ‘mk’
224 | mk(u) += d;
| ^~
answer.code: At global scope:
answer.code:235:6: error: redefinition of ‘void upd(long long int, long long int, long long int)’
235 | void upd(int u,int x,int d)
| ^~~
answer.code:37:6: note: ‘void upd(long long int, long long int, long long int)’ previously defined here
37 | void upd(int u,int x,int d)
| ^~~
answer.code:251:6: error: redefinition of ‘node que(long long int, long long int, long long int)’
251 | node que(int u,int l,int r)
| ^~~
answer.code:53:6: note: ‘node que(long long int, long long int, long long int)’ previously defined here
53 | node que(int u,int l,int r)
| ^~~
answer.code: In function ‘node que(long long int, long long int, long long int)’:
answer.code:260:40: error: t...