QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#59708 | #2827. Autobiography | XrkArul# | WA | 50ms | 3584kb | C++17 | 2.3kb | 2022-10-31 21:18:41 | 2022-10-31 21:18:45 |
Judging History
answer
// Duet of Dusk Embers--XrkArul
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ULL __int128_t
#define ull unsigned long long
#define vi vector<int>
#define vll vector<ll>
#define endl '\n'
#define ednl '\n'
#define pb push_back
#define fi first
#define se second
#define ls (p<<1)
#define rs (p<<1|1)
#define fix setprecision
#define all(v) (v).begin(),(v).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define debug(x) cerr<<#x<<':'<<' '<<x<<'\n'
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define pq priority_queue<int, vector<int>>
#define PQ priority_queue<int, vector<int>, greater<int>>
const ll inf = 1e18;
const ll mod=1e9+7;
const ull hashbase = 5767169;
ll powmod(ll a,ll b){ll s=1;a%=mod;while(b){if(b&1)s=s*a%mod;b>>=1;a=a*a%mod;}return s%mod;}
#define int long long
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
// cin>>n>>m;
while(cin>>n>>m){
// cin>>n>>m;
string s;cin>>s;
vector<int> d(n+1);
rep(i,0,s.size()-1)d[i+1]=s[i]-'a';
vector<vi> e(n+1);
while(m--){
int a,b;cin>>a>>b;
// if(a>n||b>n)continue;
if(d[a]!=d[b]){
e[a].pb(b);
e[b].pb(a);
}
}
int ans=0;vector<vi> cnt(n+1,vi(5));vi vis(n+1);
function<void(int)> dfs1=[&](int x){
vis[x]=1;
for(auto v:e[x]){
if(d[x]!='b'-'a')// o
{
cnt[x][2]+=(int)e[v].size()-1;
}
if(vis[v])continue;
dfs1(v);
}
};
rep(i,1,n)if(!vis[i])
dfs1(1);fill(all(vis),0);
function<void(int)> dfs=[&](int x){
vis[x]=1;
for(auto v:e[x]){
if(d[x]=='b'-'a')// b
{
cnt[x][1]+=cnt[v][2]-((int)e[x].size()-1);
}
if(vis[v])continue;
dfs(v);
}
};
rep(i,1,n){
if(!vis[i])dfs(i);
}
// dfs(1);
rep(i,1,n){
if(d[i]=='b'-'a')ans+=cnt[i][1];
}
cout<<ans<<endl;
}
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3584kb
input:
5 4 bbobo 1 3 2 3 3 4 4 5 4 6 bobo 1 2 1 3 1 4 2 3 2 4 3 4 4 0 bobo
output:
2 4 0
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 50ms
memory: 3512kb
input:
4 4 oobo 2 3 4 1 4 3 3 1 4 3 obob 1 4 2 3 1 2 4 4 obob 3 1 2 3 2 1 1 4 4 3 bboo 2 4 4 1 3 4 4 3 bbbo 1 4 1 3 4 2 4 4 obbo 3 4 2 4 2 3 3 1 4 3 bobo 2 3 4 3 1 4 4 3 obbb 3 4 4 2 1 4 4 5 bobo 4 1 2 1 3 1 4 3 2 4 4 4 obbo 3 4 3 1 2 3 1 4 4 3 bobb 4 2 4 1 2 3 4 3 obbo 3 1 3 2 1 2 4 4 ooob 2 1 3 1 3 4 1 4...
output:
0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 -2 0 0 1 0 0 0 0 0 -2 0 0 1 0 4 1 0 0 0 1 -2 -2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 -2 0 0 -2 0 0 0 1 0 1 0 0 0 0 0 0 4 1 0 0 0 0 4 -2 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 -2 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 0 -2 0 1...
result:
wrong answer 10th lines differ - expected: '0', found: '1'