QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#59708#2827. AutobiographyXrkArul#WA 50ms3584kbC++172.3kb2022-10-31 21:18:412022-10-31 21:18:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-31 21:18:45]
  • 评测
  • 测评结果:WA
  • 用时:50ms
  • 内存:3584kb
  • [2022-10-31 21:18:41]
  • 提交

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'