oj.uz

Submission #472926

# Submission time Handle Problem Language Result Execution time Memory
472926 2021-09-14T14:52:10 Z MohamedFaresNebili Regions (IOI09_regions) C++14
0 / 100
 105 ms 26552 KB 
#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()) { printf("%d\n", dp[{a, b}]); 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; printf("%d\n", res);
            }
            return 0;
        }

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |             scanf("%d%d%d", &n, &r, &q);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |             scanf("%d", &arr[1]); home[arr[1]].pb(1);
      |             ~~~~~^~~~~~~~~~~~~~~
regions.cpp:47:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |                 int a, h; scanf("%d%d", &a, &h); home[h].pb(l);
      |                           ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:52:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |                 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 3 ms 6108 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 6116 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 6216 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6188 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
9 Execution timed out 6 ms 6600 KB Time limit exceeded (wall clock)
10 Execution timed out 8 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 12 ms 7496 KB Time limit exceeded (wall clock)
13 Execution timed out 13 ms 7496 KB Time limit exceeded (wall clock)
14 Execution timed out 16 ms 7880 KB Time limit exceeded (wall clock)
15 Execution timed out 18 ms 10304 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 38 ms 10816 KB Time limit exceeded (wall clock)
2 Execution timed out 41 ms 10688 KB Time limit exceeded (wall clock)
3 Execution timed out 36 ms 12540 KB Time limit exceeded (wall clock)
4 Execution timed out 17 ms 8008 KB Time limit exceeded (wall clock)
5 Execution timed out 21 ms 9368 KB Time limit exceeded (wall clock)
6 Execution timed out 26 ms 9416 KB Time limit exceeded (wall clock)
7 Execution timed out 36 ms 10436 KB Time limit exceeded (wall clock)
8 Execution timed out 45 ms 15040 KB Time limit exceeded (wall clock)
9 Execution timed out 77 ms 15936 KB Time limit exceeded (wall clock)
10 Execution timed out 86 ms 20532 KB Time limit exceeded (wall clock)
11 Execution timed out 103 ms 18436 KB Time limit exceeded (wall clock)
12 Execution timed out 104 ms 16864 KB Time limit exceeded (wall clock)
13 Execution timed out 98 ms 17824 KB Time limit exceeded (wall clock)
14 Execution timed out 105 ms 17980 KB Time limit exceeded (wall clock)
15 Execution timed out 97 ms 21256 KB Time limit exceeded (wall clock)
16 Execution timed out 99 ms 26552 KB Time limit exceeded (wall clock)
17 Execution timed out 102 ms 25268 KB Time limit exceeded (wall clock)