QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#950355 | #9805. Guide Map | BenjaminJ | WA | 1ms | 3712kb | C++14 | 2.6kb | 2025-03-25 07:39:26 | 2025-03-25 07:39:27 |
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;
}
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'