oj.uz

Submission #472921

# Submission time Handle Problem Language Result Execution time Memory
472921 2021-09-14T14:46:39 Z MohamedFaresNebili Regions (IOI09_regions) C++14
0 / 100
 109 ms 26556 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", &n, &r, &q);
            scanf("%d\n", &arr[1]); home[arr[1]].pb(1);
            for(int l=2;l<=n;l++) {
                int a, h; scanf("%d%d\n", &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\n", &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", &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\n", &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\n", &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\n", &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 6 ms 6600 KB Time limit exceeded (wall clock)
10 Execution timed out 8 ms 6780 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 6984 KB Time limit exceeded (wall clock)
12 Execution timed out 11 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 23 ms 10280 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 31 ms 10816 KB Time limit exceeded (wall clock)
2 Execution timed out 38 ms 10688 KB Time limit exceeded (wall clock)
3 Execution timed out 37 ms 12612 KB Time limit exceeded (wall clock)
4 Execution timed out 19 ms 8068 KB Time limit exceeded (wall clock)
5 Execution timed out 24 ms 9416 KB Time limit exceeded (wall clock)
6 Execution timed out 27 ms 9344 KB Time limit exceeded (wall clock)
7 Execution timed out 44 ms 10444 KB Time limit exceeded (wall clock)
8 Execution timed out 48 ms 15108 KB Time limit exceeded (wall clock)
9 Execution timed out 77 ms 15936 KB Time limit exceeded (wall clock)
10 Execution timed out 81 ms 20544 KB Time limit exceeded (wall clock)
11 Execution timed out 103 ms 18408 KB Time limit exceeded (wall clock)
12 Execution timed out 101 ms 16876 KB Time limit exceeded (wall clock)
13 Execution timed out 94 ms 17680 KB Time limit exceeded (wall clock)
14 Execution timed out 109 ms 17984 KB Time limit exceeded (wall clock)
15 Execution timed out 99 ms 21232 KB Time limit exceeded (wall clock)
16 Execution timed out 106 ms 26556 KB Time limit exceeded (wall clock)
17 Execution timed out 95 ms 25268 KB Time limit exceeded (wall clock)