fork download
copy 
  1. #include<bits/stdc++.h>
  2. // #include <sys/resource.h>
  3.  
  4. #define ll long long
  5. // #define ll int
  6. #define f(i,a,b) for(int i=a;i<b;i++)
  7. #define mod 1000000007
  8. // #define mod 998244353 
  9. #define mp make_pair
  10. #define uniq(v) (v).erase(unique(all(v)),(v).end())
  11. #define ff first
  12. #define ss second
  13. #define rf(i,a,b) for(int i=a;i>=b;i--)
  14. #define sc(a) scanf("%lld",&a)
  15. #define pf printf
  16. #define sz(a) (int)(a.size())
  17. #define psf push_front
  18. #define ppf pop_front
  19. #define ppb pop_back
  20. #define pb push_back
  21. #define pq priority_queue
  22. #define all(s) s.begin(),s.end()
  23. #define sp(a) setprecision(a)
  24. #define rz resize
  25. #define ld long double
  26. #define inf (ll)1e18
  27. #define ub upper_bound
  28. #define lb lower_bound
  29. #define bs binary_search
  30. #define eb emplace_back
  31. const double pi = acos(-1);
  32. ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
  33. // ll binpow(ll a, ll b, ll md){ll res=1;a%=mod;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
  34.  
  35. using namespace std;
  36.  
  37. const int N=512;
  38. int n,timer=0;
  39. vector<vector<int> > v;
  40. vector<int> st,en,a,freq,tot,cnt;
  41. vector<bool> vis;
  42.  
  43. void dfs(int cur, int parent)
  44. {
  45.     st[cur]=timer++;
  46.     a.pb(cur);
  47.     f(i,0,sz(v[cur]))
  48.     {
  49.         int node=v[cur][i];
  50.         if(node!=parent)
  51.             dfs(node,cur);
  52.     }
  53.     en[cur]=timer-1;
  54. }
  55.  
  56. struct Query {
  57.     int l, r, idx;
  58.     bool operator<(Query other) const
  59.     {
  60.         return make_pair(l / N, r) <
  61.                make_pair(other.l / N, other.r);
  62.     }
  63. };
  64.  
  65. int main()
  66. {
  67.     ios_base::sync_with_stdio(false);
  68.     cin.tie(NULL);
  69.     // freopen("input.txt","r",stdin);
  70.     // freopen("output.txt","w",stdout);
  71. // #ifndef ONLINE_JUDGE
  72.     // freopen("chainblock_input.txt","r",stdin);
  73.     // freopen("output.txt","w",stdout);
  74. // #endif
  75.     int z=1;
  76.     cin>>z;
  77.     int mx=0;
  78.     f(i,1,z+1)
  79.     {
  80.         timer=0;
  81.         cout<<"Case #"<<i<<": ";
  82.         cin>>n;
  83.         v.clear(),st.clear(),en.clear(),freq.clear(),cnt.clear();
  84.         v.rz(n+2),st.rz(n+2),en.rz(n+2),freq.rz(n+2),cnt.rz(n+2);
  85.         f(j,0,n-1)
  86.         {
  87.             int l,r;
  88.             cin>>l>>r;
  89.             v[l].pb(r),v[r].pb(l);
  90.         }
  91.         f(i,1,n+1)
  92.         {
  93.             cin>>freq[i];
  94.             cnt[freq[i]]++;
  95.         }
  96.         dfs(1,1);
  97.         tot.clear();
  98.         tot.rz(n+1);
  99.         vector<Query> queries;
  100.         f(i,2,n+1)
  101.             queries.pb({st[i],en[i],i-2});
  102.         sort(all(queries));
  103.         int cur_l = 0;
  104.         int cur_r = -1,ans=0,cur=0;
  105.         for (Query q : queries) {
  106.             while (cur_l > q.l) {
  107.                 cur_l--;
  108.                 // add(cur_l);
  109.                 int fr=freq[a[cur_l]];
  110.                 if(tot[fr]==0)
  111.                     cur++;
  112.                 tot[fr]++;
  113.                 if(tot[fr]==cnt[fr])
  114.                     cur--;
  115.             }
  116.             while (cur_r < q.r) {
  117.                 cur_r++;
  118.                 //add(cur_r);
  119.                 int fr=freq[a[cur_r]];
  120.                 if(tot[fr]==0)
  121.                     cur++;
  122.                 tot[fr]++;
  123.                 if(tot[fr]==cnt[fr])
  124.                     cur--;
  125.             }
  126.             while (cur_l < q.l) {
  127.                 //remove(cur_l);
  128.                 int fr=freq[a[cur_l]];
  129.                 if(tot[fr]==1)
  130.                     cur--;
  131.                 if(tot[fr]==cnt[fr])
  132.                     cur++;
  133.                 tot[fr]--;
  134.                 cur_l++;
  135.             }
  136.             while (cur_r > q.r) {
  137.                 //remove(cur_r);
  138.                 int fr=freq[a[cur_r]];
  139.                 if(tot[fr]==1)
  140.                     cur--;
  141.                 if(tot[fr]==cnt[fr])
  142.                     cur++;
  143.                 tot[fr]--;
  144.                 cur_r--;
  145.             }
  146.             if(cur==0)
  147.                 ans++;
  148.         }
  149.         cout<<ans<<"\n";
  150.         a.clear();
  151.     }
  152. }
Success #stdin #stdout 0.01s 5508KB
comments (?)
stdin
copy 
6
2
1 2
1 1
2
1 2
1 2
3
1 2
1 3
2 2 3
3
1 2
1 3
2 3 3
6
2 5
4 1
1 3
5 1
3 6
2 3 5 5 6 2
10
10 7
2 8
7 9
7 3
1 3
3 8
8 5
5 6
6 4
5 3 3 4 6 3 10 6 8 8
stdout
copy 
Case #1: 0
Case #2: 1
Case #3: 1
Case #4: 0
Case #5: 2
Case #6: 3
https://ideone.com/hlTvaM
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!