oj.uz

Submission #472945

# Submission time Handle Problem Language Result Execution time Memory
472945 2021-09-14T15:42:28 Z MohamedFaresNebili Regions (IOI09_regions) C++14
0 / 100
 130 ms 26560 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2")

        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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 6088 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
8 Execution timed out 5 ms 6216 KB Time limit exceeded (wall clock)
9 Execution timed out 8 ms 6600 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 6728 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 6984 KB Time limit exceeded (wall clock)
12 Execution timed out 13 ms 7496 KB Time limit exceeded (wall clock)
13 Execution timed out 13 ms 7552 KB Time limit exceeded (wall clock)
14 Execution timed out 19 ms 7924 KB Time limit exceeded (wall clock)
15 Execution timed out 24 ms 10240 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 38 ms 10916 KB Time limit exceeded (wall clock)
2 Execution timed out 36 ms 10628 KB Time limit exceeded (wall clock)
3 Execution timed out 50 ms 12608 KB Time limit exceeded (wall clock)
4 Execution timed out 17 ms 8072 KB Time limit exceeded (wall clock)
5 Execution timed out 19 ms 9416 KB Time limit exceeded (wall clock)
6 Execution timed out 26 ms 9352 KB Time limit exceeded (wall clock)
7 Execution timed out 47 ms 10484 KB Time limit exceeded (wall clock)
8 Execution timed out 44 ms 15076 KB Time limit exceeded (wall clock)
9 Execution timed out 74 ms 16012 KB Time limit exceeded (wall clock)
10 Execution timed out 77 ms 20468 KB Time limit exceeded (wall clock)
11 Execution timed out 114 ms 18368 KB Time limit exceeded (wall clock)
12 Execution timed out 104 ms 16844 KB Time limit exceeded (wall clock)
13 Execution timed out 94 ms 17584 KB Time limit exceeded (wall clock)
14 Execution timed out 111 ms 17984 KB Time limit exceeded (wall clock)
15 Execution timed out 102 ms 21224 KB Time limit exceeded (wall clock)
16 Execution timed out 130 ms 26560 KB Time limit exceeded (wall clock)
17 Execution timed out 116 ms 25368 KB Time limit exceeded (wall clock)