QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#950383#9805. Guide MapBenjaminJWA 5ms11120kbC++145.0kb2025-03-25 08:58:162025-03-25 08:58:16

Judging History

This is the latest submission verdict.

  • [2025-03-25 08:58:16]
  • Judged
  • Verdict: WA
  • Time: 5ms
  • Memory: 11120kb
  • [2025-03-25 08:58:16]
  • Submitted

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'