oj.uz

답안 #805723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
805723 2023-08-03T21:31:35 Z HD1 Monthly railway pass (LMIO18_menesinis_bilietas) C++14
100 / 100
 689 ms 101616 KB 
// we all are lost trying to be someone.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_studio(0); cin.tie(0);
#define sz(x) ll(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define ss second
#define ff first
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
const int MAX=1e6;
const int inf=1e9;
const int mod=1e9+7;
vector<ll> gfo1[MAX];
vector<ll> gfo2[MAX];
vector<ii> s;
vector<ll> c;
bool vst[MAX];
ll tam[MAX], p[MAX];
set<ii> z;
void dfsmark(ll u, ll x){
    p[u]=x;
    tam[x]++;
    vst[u]=true;
    for(ll v:gfo1[u]){
        if(!vst[v]){
            dfsmark(v,x);
        }
    }
}
void solve(){
    ll n, m, u, v;
    char x;
    cin>>n>>m;
    for(ll i=0; i<m; i++){
        cin>>u>>v>>x;
        if(x=='A'){
            s.pb({u,v});
        }
        else{
            gfo1[u].pb(v);
            gfo1[v].pb(u);        
        }
    }
    ll cont=1;
    for(ll i=1; i<=n; i++){
        if(!vst[i]) {
            dfsmark(i,cont);
            cont++;
        }
    }
    cont--;
    if(cont==1){
        cout<<n<<endl;
        return;
    }
    for(ii x:s){
        u=p[x.ff];
        v=p[x.ss];
        if(u!=v && !(z.count({min(u,v),max(u,v)}))){
            gfo2[u].pb(v);
            gfo2[v].pb(u);
            z.insert({min(u,v),max(u,v)});
        }
    }
    ll ans=0;
    for(ll i=1; i<=cont; i++){
        if(sz(gfo2[i])==cont-1)ans+=tam[i];
    }
    cout<<ans<<endl;  
    return;
}
int main(){
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 71748 KB Output is correct
2 Correct 20 ms 47216 KB Output is correct
3 Correct 20 ms 47316 KB Output is correct
4 Correct 26 ms 55056 KB Output is correct
5 Correct 20 ms 47444 KB Output is correct
6 Correct 110 ms 52444 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 55056 KB Output is correct
2 Correct 20 ms 47444 KB Output is correct
3 Correct 19 ms 47276 KB Output is correct
4 Correct 21 ms 47400 KB Output is correct
5 Correct 28 ms 48096 KB Output is correct
6 Correct 440 ms 82348 KB Output is correct
7 Correct 689 ms 101616 KB Output is correct
8 Correct 33 ms 49224 KB Output is correct
9 Correct 47 ms 50564 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 47216 KB Output is correct
2 Correct 20 ms 47316 KB Output is correct
3 Correct 19 ms 47276 KB Output is correct
4 Correct 21 ms 47400 KB Output is correct
5 Correct 28 ms 48096 KB Output is correct
6 Correct 20 ms 47268 KB Output is correct
7 Correct 20 ms 47200 KB Output is correct
8 Correct 21 ms 47316 KB Output is correct
9 Correct 22 ms 47480 KB Output is correct
10 Correct 25 ms 47656 KB Output is correct
11 Correct 22 ms 47572 KB Output is correct
12 Correct 19 ms 47332 KB Output is correct
13 Correct 20 ms 47212 KB Output is correct
14 Correct 25 ms 47668 KB Output is correct
15 Correct 20 ms 47188 KB Output is correct
16 Correct 21 ms 47348 KB Output is correct
17 Correct 20 ms 47252 KB Output is correct
18 Correct 21 ms 47348 KB Output is correct
19 Correct 20 ms 47344 KB Output is correct
20 Correct 21 ms 47444 KB Output is correct

Subtask #4
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 47268 KB Output is correct
2 Correct 20 ms 47200 KB Output is correct
3 Correct 21 ms 47316 KB Output is correct
4 Correct 22 ms 47480 KB Output is correct
5 Correct 25 ms 47656 KB Output is correct
6 Correct 22 ms 47572 KB Output is correct
7 Correct 19 ms 47332 KB Output is correct
8 Correct 20 ms 47212 KB Output is correct
9 Correct 25 ms 47668 KB Output is correct
10 Correct 20 ms 47188 KB Output is correct
11 Correct 21 ms 47348 KB Output is correct
12 Correct 20 ms 47252 KB Output is correct
13 Correct 21 ms 47348 KB Output is correct
14 Correct 20 ms 47344 KB Output is correct
15 Correct 21 ms 47444 KB Output is correct
16 Correct 20 ms 47216 KB Output is correct
17 Correct 20 ms 47316 KB Output is correct
18 Correct 19 ms 47276 KB Output is correct
19 Correct 21 ms 47400 KB Output is correct
20 Correct 28 ms 48096 KB Output is correct
21 Correct 20 ms 47444 KB Output is correct
22 Correct 33 ms 49224 KB Output is correct
23 Correct 47 ms 50564 KB Output is correct
24 Correct 110 ms 52444 KB Output is correct
25 Correct 38 ms 47896 KB Output is correct
26 Correct 221 ms 56188 KB Output is correct
27 Correct 87 ms 51400 KB Output is correct
28 Correct 159 ms 60124 KB Output is correct
29 Correct 71 ms 49568 KB Output is correct
30 Correct 148 ms 59116 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 47268 KB Output is correct
2 Correct 20 ms 47200 KB Output is correct
3 Correct 21 ms 47316 KB Output is correct
4 Correct 22 ms 47480 KB Output is correct
5 Correct 25 ms 47656 KB Output is correct
6 Correct 22 ms 47572 KB Output is correct
7 Correct 19 ms 47332 KB Output is correct
8 Correct 20 ms 47212 KB Output is correct
9 Correct 25 ms 47668 KB Output is correct
10 Correct 20 ms 47188 KB Output is correct
11 Correct 21 ms 47348 KB Output is correct
12 Correct 20 ms 47252 KB Output is correct
13 Correct 21 ms 47348 KB Output is correct
14 Correct 20 ms 47344 KB Output is correct
15 Correct 21 ms 47444 KB Output is correct
16 Correct 38 ms 47896 KB Output is correct
17 Correct 221 ms 56188 KB Output is correct
18 Correct 87 ms 51400 KB Output is correct
19 Correct 159 ms 60124 KB Output is correct
20 Correct 71 ms 49568 KB Output is correct
21 Correct 148 ms 59116 KB Output is correct
22 Correct 405 ms 71748 KB Output is correct
23 Correct 20 ms 47216 KB Output is correct
24 Correct 20 ms 47316 KB Output is correct
25 Correct 26 ms 55056 KB Output is correct
26 Correct 19 ms 47276 KB Output is correct
27 Correct 21 ms 47400 KB Output is correct
28 Correct 28 ms 48096 KB Output is correct
29 Correct 20 ms 47444 KB Output is correct
30 Correct 440 ms 82348 KB Output is correct
31 Correct 689 ms 101616 KB Output is correct
32 Correct 33 ms 49224 KB Output is correct
33 Correct 47 ms 50564 KB Output is correct
34 Correct 110 ms 52444 KB Output is correct
35 Correct 60 ms 50360 KB Output is correct
36 Correct 335 ms 60588 KB Output is correct
37 Correct 185 ms 55504 KB Output is correct