oj.uz

답안 #498202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498202 2021-12-24T15:25:31 Z Kipras Monthly railway pass (LMIO18_menesinis_bilietas) C++14
81 / 100
 3000 ms 78444 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxN = 1e5*5+1;

int n, m;
vector<pair<bool, int>> adj[maxN];
int par[maxN];
int s[maxN];
vector<int> routes[maxN];
bool checkedContainer[maxN];

int find(int a){
    if(par[a]==a)return a;
    return par[a]=find(par[a]);
}

void unite(int a, int b){
    a = find(a), b = find(b);
    if(a==b)return;
    par[b]=a;
    s[a]+=s[b];
}

bool same(int a, int b){
    return find(a)==find(b);
}

int main()
{

    ios_base::sync_with_stdio(0);cin.tie(nullptr);

    cin>>n>>m;

    for(int i = 0; i < m; i++){
        int a, b;
        char t;
        bool type;
        cin>>a>>b>>t;
        if(t=='A')type=0;
        else type=1;
        adj[a].push_back({type, b});
        adj[b].push_back({type, a});
    }

    for(int i = 0; i < maxN; i++)par[i]=i;
    for(int i = 0; i < maxN; i++)s[i]=1;

    for(int i = 1; i <= n; i++){
        for(auto x : adj[i]){
            if(x.first==0){

            }else{
                unite(x.second, i);
            }
        }
    }



    for(int i = 1; i <= n; i++){
        for(auto x : adj[i]){
            if(x.first==0){
                routes[find(i)].push_back(find(x.second));
                routes[find(x.second)].push_back(find(i));
            }else{

            }
        }
    }

    int ans=0;

    for(int i = 1; i <= n; i++){
        if(checkedContainer[find(i)])continue;
        int ss=s[find(i)];
        set<int> checked;

        for(auto x : routes[find(i)]){
            if(!same(i, x)&&checked.find(find(x))==checked.end()){
                ss+=s[find(x)];
            }
            checked.insert(find(x));
        }
        if(ss==n){
            ans+=s[find(i)];
            checkedContainer[find(i)]=true;
        }
    }

    cout<<ans;


    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 42656 KB Output is correct
2 Correct 14 ms 27596 KB Output is correct
3 Correct 16 ms 27664 KB Output is correct
4 Correct 20 ms 27596 KB Output is correct
5 Correct 16 ms 27588 KB Output is correct
6 Correct 60 ms 32436 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 27596 KB Output is correct
2 Correct 16 ms 27588 KB Output is correct
3 Correct 15 ms 27724 KB Output is correct
4 Correct 16 ms 27724 KB Output is correct
5 Correct 20 ms 28016 KB Output is correct
6 Correct 354 ms 42856 KB Output is correct
7 Correct 877 ms 78444 KB Output is correct
8 Correct 27 ms 29544 KB Output is correct
9 Correct 37 ms 29956 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27596 KB Output is correct
2 Correct 16 ms 27664 KB Output is correct
3 Correct 15 ms 27724 KB Output is correct
4 Correct 16 ms 27724 KB Output is correct
5 Correct 20 ms 28016 KB Output is correct
6 Correct 15 ms 27596 KB Output is correct
7 Correct 15 ms 27656 KB Output is correct
8 Correct 17 ms 27804 KB Output is correct
9 Correct 17 ms 28004 KB Output is correct
10 Correct 23 ms 28228 KB Output is correct
11 Correct 22 ms 28008 KB Output is correct
12 Correct 15 ms 27724 KB Output is correct
13 Correct 15 ms 27724 KB Output is correct
14 Correct 28 ms 28216 KB Output is correct
15 Correct 15 ms 27596 KB Output is correct
16 Correct 17 ms 27820 KB Output is correct
17 Correct 16 ms 27704 KB Output is correct
18 Correct 16 ms 27828 KB Output is correct
19 Correct 15 ms 27724 KB Output is correct
20 Correct 18 ms 27852 KB Output is correct

Subtask #4
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 27596 KB Output is correct
2 Correct 15 ms 27656 KB Output is correct
3 Correct 17 ms 27804 KB Output is correct
4 Correct 17 ms 28004 KB Output is correct
5 Correct 23 ms 28228 KB Output is correct
6 Correct 22 ms 28008 KB Output is correct
7 Correct 15 ms 27724 KB Output is correct
8 Correct 15 ms 27724 KB Output is correct
9 Correct 28 ms 28216 KB Output is correct
10 Correct 15 ms 27596 KB Output is correct
11 Correct 17 ms 27820 KB Output is correct
12 Correct 16 ms 27704 KB Output is correct
13 Correct 16 ms 27828 KB Output is correct
14 Correct 15 ms 27724 KB Output is correct
15 Correct 18 ms 27852 KB Output is correct
16 Correct 14 ms 27596 KB Output is correct
17 Correct 16 ms 27664 KB Output is correct
18 Correct 15 ms 27724 KB Output is correct
19 Correct 16 ms 27724 KB Output is correct
20 Correct 20 ms 28016 KB Output is correct
21 Correct 16 ms 27588 KB Output is correct
22 Correct 27 ms 29544 KB Output is correct
23 Correct 37 ms 29956 KB Output is correct
24 Correct 60 ms 32436 KB Output is correct
25 Correct 33 ms 29388 KB Output is correct
26 Correct 1047 ms 45132 KB Output is correct
27 Correct 133 ms 34916 KB Output is correct
28 Correct 190 ms 37588 KB Output is correct
29 Correct 71 ms 33432 KB Output is correct
30 Correct 859 ms 35956 KB Output is correct

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 27596 KB Output is correct
2 Correct 15 ms 27656 KB Output is correct
3 Correct 17 ms 27804 KB Output is correct
4 Correct 17 ms 28004 KB Output is correct
5 Correct 23 ms 28228 KB Output is correct
6 Correct 22 ms 28008 KB Output is correct
7 Correct 15 ms 27724 KB Output is correct
8 Correct 15 ms 27724 KB Output is correct
9 Correct 28 ms 28216 KB Output is correct
10 Correct 15 ms 27596 KB Output is correct
11 Correct 17 ms 27820 KB Output is correct
12 Correct 16 ms 27704 KB Output is correct
13 Correct 16 ms 27828 KB Output is correct
14 Correct 15 ms 27724 KB Output is correct
15 Correct 18 ms 27852 KB Output is correct
16 Correct 33 ms 29388 KB Output is correct
17 Correct 1047 ms 45132 KB Output is correct
18 Correct 133 ms 34916 KB Output is correct
19 Correct 190 ms 37588 KB Output is correct
20 Correct 71 ms 33432 KB Output is correct
21 Correct 859 ms 35956 KB Output is correct
22 Correct 355 ms 42656 KB Output is correct
23 Correct 14 ms 27596 KB Output is correct
24 Correct 16 ms 27664 KB Output is correct
25 Correct 20 ms 27596 KB Output is correct
26 Correct 15 ms 27724 KB Output is correct
27 Correct 16 ms 27724 KB Output is correct
28 Correct 20 ms 28016 KB Output is correct
29 Correct 16 ms 27588 KB Output is correct
30 Correct 354 ms 42856 KB Output is correct
31 Correct 877 ms 78444 KB Output is correct
32 Correct 27 ms 29544 KB Output is correct
33 Correct 37 ms 29956 KB Output is correct
34 Correct 60 ms 32436 KB Output is correct
35 Correct 672 ms 30616 KB Output is correct
36 Execution timed out 3082 ms 47468 KB Time limit exceeded
37 Halted 0 ms 0 KB -