QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#950355#9805. Guide MapBenjaminJWA 1ms3712kbC++142.6kb2025-03-25 07:39:262025-03-25 07:39:27

Judging History

This is the latest submission verdict.

  • [2025-03-25 07:39:27]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3712kb
  • [2025-03-25 07:39:26]
  • 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;
}

V<vi> adj;
vb found;
int MOD = 998244353;
int size2;

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 dfs1(int v){
    found[v]=true;
    for(int u : adj[v]){
        if(!found[u])dfs1(u);
    }
}

vi cnts;
int ans = 0;
int mult = 0;

void dfs(int v, int p=-1, int cnt=0){
    // cout << ans << endl;
    // cout << v << " " << cnt << "\n";
    for(int u : adj[v]){
        if(u==p)continue;
        //calculate uscore
        cnt+=size2-cnts[u];
        ans += binex(2,cnt)*mult;
        ans%=MOD;
        dfs(u,v,cnt);
        cnt-=size2-cnts[u];
    }
}

void solve(){
    int n; 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);
    vi c2;
    dfs1(0);
    REP(i,0,n-1){
        if(!found[i])c2.pb(i);
    }
    size2=sz(c2);
    cnts=vi(n,0);
    for(int x : c2){
        cnts[x]++;
    }
    REP(i,1,n-1){
        cnts[i]+=cnts[i-1];
    }
    mult=max(binex(2,size2)-1,2ll);
    ans=mult;
    dfs(0);
    cout << ans << endl;
    // printv(c2);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--)solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

4
1 4
2 3

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

2

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3712kb

input:

4
1 2
1 3

output:

10

result:

wrong answer 1st numbers differ - expected: '6', found: '10'