QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#950383 | #9805. Guide Map | BenjaminJ | WA | 5ms | 11120kb | C++14 | 5.0kb | 2025-03-25 08:58:16 | 2025-03-25 08:58:16 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define V vector
#define vi vector<int>
#define vl vector<long long>
#define vb vector<bool>
#define vs vector<string>
#define vd vector<double>
#define pi pair<int,int>
#define pd pair<double,double>
#define pl pair<long long, long long>
#define all(i) i.begin(),i.end()
#define REP(i,a,b) for(int i = a; i <= b; i++)
#define PER(i,a,b) for(int i = a; i >= b; i--)
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define indlb(v, x, c) (distance((v).begin(), lower_bound((v).begin(), (v).end(), (x),c)))
#define indub(v, x, c) (distance((v).begin(), upper_bound((v).begin(), (v).end(), (x),c)))
#define sz(i) (int) i.size()
#define smax(a,b) a=max(a,b)
#define smin(a,b) a=min(a,b)
#define currtime chrono::high_resolution_clock::now().time_since_epoch().count()
#define int long long
#define double long double
template<typename T>
void printv(V<T> x){
for(T i : x)cout << i << " ";
cout << "\n";
}
template<typename T>
void readv(V<T> &x){
for(T &y : x)cin>>y;
}
constexpr int MX_NODES = 3e7;
constexpr int RANGE_SZ = 2e5+5;
int tree[MX_NODES], l[MX_NODES], r[MX_NODES];
int timer = -1;
int build(int tl, int tr) {
const int cur = ++timer;
if (tl == tr) {
tree[timer] = 0 ;
return cur;
}
int mid = (tl + tr) / 2;
l[cur] = build(tl, mid);
r[cur] = build(mid+1, tr);
tree[cur] = tree[l[cur]] + tree[r[cur]];
return cur;
}
int upd(int pos, int add, int v, int tl = 0, int tr = RANGE_SZ - 1) {
const int cur = ++timer;
if (tl == tr) {
tree[cur] = add + tree[v];
return cur;
}
l[cur] = l[v], r[cur] = r[v];
const int mid = tl + (tr - tl) / 2;
if (pos > mid) {
r[cur] = upd(pos, add, r[v], mid + 1, tr);
} else {
l[cur] = upd(pos, add, l[v], tl, mid);
}
tree[cur] = tree[l[cur]] + tree[r[cur]];
return cur;
}
int query(int v, int l1,int r1, int tl = 0, int tr = RANGE_SZ - 1) {
if(l1<=tl && tr<=r1) return tree[v];
const int mid = tl + (tr - tl) / 2;
int sum = 0;
if(mid>=l1) sum+= query(l[v], l1, r1, tl, mid);
if(mid<r1)sum+= query(r[v],l1,r1,mid+1,tr);
return sum;
}
V<vi> adj;
int MOD = 998244353;
vb found;
ll binex(ll b, ll e){
b%=MOD;
ll ans = 1;
while(e > 0){
if(e%2==1)ans*=b;
e/=2;
b=b*b;
b%=MOD;
ans%=MOD;
}
return ans;
}
void dfs(int v){
found[v]=true;
for(int u : adj[v])if(!found[u])dfs(u);
}
vi roots;
vi in;
vi out;
int ti=1;
vi c2;
bool flag=true;
void dfs2(int v){
if(flag)c2.pb(v);
in[v]=ti;
found[v]=true;
for(int u : adj[v]){
if(!found[u])dfs2(u);
}
out[v]=ti;
roots.pb(upd(v,1,roots.back()));
ti++;
}
int cnt = 0;
int n;
void dfs3(int v, int p=-1){
for(int u : adj[v]){
if(u==p)continue;
int a = query(roots[out[u]],u,n-1)-query(roots[in[u]-1],u,n-1)-1;
cnt+=a;
dfs3(u,v);
}
}
vi scores;
void dfs4(int v, int p = -1){
scores[v]=cnt;
for(int u : adj[v]){
if(u==p)continue;
int a = query(roots[out[u]],u,n-1)-query(roots[in[u]-1],u,n-1)-1;
int b = query(roots[in[u]-1],v,n-1)+query(roots.back(),v,n-1)-query(roots[out[u]],v,n-1)-1;
int c = b-a;
cnt+=c;
dfs4(u,v);
cnt-=c;
}
}
int base;
int ans = 0;
vi big;
int cnt2 = 0;
void dfs5(int v, int p=-1){
ans+=binex(2,cnt2);
ans%=MOD;
for(int u : adj[v]){
if(u==p)continue;
cnt2+=big[u];
dfs5(u,v);
cnt2-=big[u];
}
}
void solve(){
cin >> n;
adj.resize(n);
REP(i,1,n-2){
int a,b; cin >> a >> b;
a--;
b--;
adj[a].pb(b);
adj[b].pb(a);
}
REP(i,0,n-1){
sort(all(adj[i]));
}
found = vb(n,false);
dfs(0);
int r;
REP(i,0,n-1)if(!found[i]){
r=i;
break;
}
roots.pb(build(0,n-1));
in=vi(n,0);
out=vi(n,0);
dfs2(r);
dfs3(r);
scores.resize(n);
dfs4(r);
vb inc2(n,false);
for(int x : c2)inc2[x]=true;
V<pi> guys;
base=0;
int mult=1;
PER(i,n-1,0){
if(inc2[i]){
base+=(binex(2,scores[i]))*mult;
base%=MOD;
mult*=2;
mult%=MOD;
}
}
big.resize(n);
for(int x : c2)big[x]++;
PER(i,n-2,0){
big[i]+=big[i+1];
}
timer=0;
ti=1;
roots.clear();
roots.pb(build(0,n-1));
cnt=0;
flag=false;
found=vb(n,false);
dfs2(0);
dfs3(0);
dfs5(0);
ans*=base;
ans%=MOD;
if(sz(c2)==1){
ans+=binex(2,cnt);
ans%=MOD;
}
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7780kb
input:
4 1 4 2 3
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7904kb
input:
2
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7904kb
input:
4 1 2 1 3
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 0ms
memory: 7904kb
input:
4 1 3 3 2
output:
8
result:
ok 1 number(s): "8"
Test #5:
score: 0
Accepted
time: 0ms
memory: 7908kb
input:
4 1 4 4 2
output:
5
result:
ok 1 number(s): "5"
Test #6:
score: 0
Accepted
time: 0ms
memory: 7900kb
input:
4 1 2 3 4
output:
15
result:
ok 1 number(s): "15"
Test #7:
score: 0
Accepted
time: 0ms
memory: 7776kb
input:
4 3 2 2 4
output:
10
result:
ok 1 number(s): "10"
Test #8:
score: -100
Wrong Answer
time: 5ms
memory: 11120kb
input:
5000 407 334 4311 4338 2530 2578 2052 1946 3803 3961 1849 1756 813 876 1417 1364 3955 3713 694 661 2682 2791 1626 1791 3913 3702 4068 4053 1239 1264 2848 2682 4995 4979 3609 3604 3496 3434 229 162 4178 4769 3908 3874 4891 4920 2401 2249 2682 2853 4294 4336 4494 4478 2815 2682 4925 4928 912 914 2257 ...
output:
178078356
result:
wrong answer 1st numbers differ - expected: '574627696', found: '178078356'