Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- #define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
- typedef long long ll;
- const long long mod = 1000000007;
- ll gcd (ll a, ll b) {return b==0 ? a : gcd(b, a%b);}
- #define all(c) (c).begin(),(c).end()
- #define pb push_back
- #define mp make_pair
- #define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
- #define debug_vector(v, n) for(int i = 0; i<n; i++)cout<< v[i] << " \n"[i == n-1]
- #define forn(i, n) for (int i = 0; i < n; i++)
- const int di4[] = {-1, 0, 1, 0};
- const int dj4[] = { 0, 1, 0, -1};
- const int di8[] = {-1, 0, 1, 0, -1, 1,-1,1};
- const int dj8[] = { 0, 1, 0, -1, -1, 1,1,-1};
- struct hash_pair {
- template <class T1, class T2>
- size_t operator()(const pair<T1, T2>& p) const
- {
- auto hash1 = hash<T1>{}(p.first);
- auto hash2 = hash<T2>{}(p.second);
- if (hash1 != hash2) {
- return hash1 ^ hash2;
- }
- return hash1;
- }
- };
- const int maxn = 2e5;
- bool vis[maxn];
- vector<vector<int>> g(26);
- void dfs(int u){
- vis[u] = true;
- for(auto v : g[u]){
- if(vis[v] == false)
- dfs(v);
- }
- }
- int main()
- {
- #ifdef LOCAL
- freopen("input.txt", "rt", stdin);
- freopen("output.txt", "wt", stdout);
- #endif
- fastio
- int tc = 1;
- cin >> tc;
- while(tc--){
- string s;
- memset(vis, false, sizeof vis);
- g = vector<vector<int>> (26);
- auto cc = [&](string c){
- int comp = 0;
- for(auto x : c){
- if(isalnum(x)){
- if(vis[x - 'A'] == false){
- dfs(x - 'A');
- comp++;
- }
- }
- }
- return comp;
- };
- while(cin >> s && s[0] != '*'){
- int u = s[1] - 'A', v = s[3] -'A';
- g[u].pb(v);
- g[v].pb(u);
- }
- cin >> s;
- int count_acorn = 0;
- for(auto x : s){
- if(isalnum(x)){
- if(g[x - 'A'].size() == 0){
- count_acorn++;
- }
- }
- }
- int ans = cc(s);
- cout << "There are "<<ans - count_acorn<< " tree(s) and "<<count_acorn<<" acorn(s)."<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement