oj.uz

Submission #472948

# Submission time Handle Problem Language Result Execution time Memory
472948 2021-09-14T15:44:09 Z MohamedFaresNebili Regions (IOI09_regions) C++14
90 / 100
 8000 ms 38592 KB 
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
 
        using namespace std;
 
        using ll  = long long;
        using ld  = long double;
        using ii  = pair<int, int>;
 
        using vl  = vector<long long>;
 
        #define mp make_pair
        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define ub upper_bound
        #define all(x) (x).begin() , (x).end()
 
        const int N = 2*100005;
        const long long MOD = 1e9+7;
        const long double EPS = 0.000000001;
        const double PI = 3.14159265358979323846;
        const int nx[4]={1, -1, 0, 0}, ny[4]={0, 0, 1, -1};
 
        long long gcd(int a, int b) { return (b==0?a:gcd(b, a%b)); }
        long long lcm(int a, int b) { return  a*(b/gcd(a, b)); }
        long long fact(int a) { return (a==1?1:a*fact(a-1)); }
 
        int n, r, q, timer=0, arr[200005], tin[200005], out[200005];
        vector<int>adj[200005], se[25005]; vector<int>home[25005]; map<ii, int>dp;
        void dfs(int v, int p) {
            tin[v]=++timer; se[arr[v]].pb(timer);
            for(auto u:adj[v]) {
                if(u==p) continue;
                dfs(u, v);
            }
            out[v]=++timer;
        }
 
        int32_t main()
        {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            scanf("%d%d%d", &n, &r, &q);
            scanf("%d", &arr[1]); home[arr[1]].pb(1);
            for(int l=2;l<=n;l++) {
                int a, h; scanf("%d%d", &a, &h); home[h].pb(l);
                adj[a].pb(l); adj[l].pb(a); arr[l]=h;
            }
            dfs(1, 1);
            while(q--) {
                int a, b; scanf("%d%d", &a, &b); int res=0;
                if(dp.find({a, b})!=dp.end()) { cout<<dp[{a, b}]<<"\n"<<flush; continue; }
                for(auto u:home[a]) {
                    int l=tin[u], r=out[u];
                    int add=lb(all(se[b]), r)-lb(all(se[b]), l);
                    res+=add;
                }
                dp[{a, b}]=res; cout<<res<<"\n"<<flush;
            }
            return 0;
        }

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |             scanf("%d%d%d", &n, &r, &q);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |             scanf("%d", &arr[1]); home[arr[1]].pb(1);
      |             ~~~~~^~~~~~~~~~~~~~~
regions.cpp:49:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |                 int a, h; scanf("%d%d", &a, &h); home[h].pb(l);
      |                           ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:54:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |                 int a, b; scanf("%d%d", &a, &b); int res=0;
      |                           ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 6 ms 6088 KB Output is correct
4 Correct 9 ms 6216 KB Output is correct
5 Correct 13 ms 6216 KB Output is correct
6 Correct 30 ms 6336 KB Output is correct
7 Correct 22 ms 6388 KB Output is correct
8 Correct 48 ms 6404 KB Output is correct
9 Correct 64 ms 6972 KB Output is correct
10 Correct 112 ms 7216 KB Output is correct
11 Correct 135 ms 7516 KB Output is correct
12 Correct 196 ms 8244 KB Output is correct
13 Correct 205 ms 8272 KB Output is correct
14 Correct 297 ms 8692 KB Output is correct
15 Correct 255 ms 11272 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1862 ms 12684 KB Output is correct
2 Correct 2098 ms 12524 KB Output is correct
3 Correct 3126 ms 16612 KB Output is correct
4 Correct 255 ms 9556 KB Output is correct
5 Correct 409 ms 11648 KB Output is correct
6 Correct 633 ms 11588 KB Output is correct
7 Correct 1085 ms 11936 KB Output is correct
8 Correct 1231 ms 19220 KB Output is correct
9 Correct 2817 ms 24304 KB Output is correct
10 Correct 4876 ms 30616 KB Output is correct
11 Correct 6003 ms 30212 KB Output is correct
12 Correct 5959 ms 22296 KB Output is correct
13 Correct 6582 ms 24896 KB Output is correct
14 Execution timed out 8050 ms 25556 KB Time limit exceeded
15 Execution timed out 8071 ms 30560 KB Time limit exceeded
16 Correct 7515 ms 38592 KB Output is correct
17 Correct 7237 ms 36800 KB Output is correct