oj.uz

Submission #472930

# Submission time Handle Problem Language Result Execution time Memory
472930 2021-09-14T14:59:07 Z MohamedFaresNebili Regions (IOI09_regions) C++14
0 / 100
 116 ms 26532 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);
            cin>>n>>r>>q; cin>>arr[1]; home[arr[1]].pb(1);
            for(int l=2;l<=n;l++) {
                int a, h; cin>>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; cin>>a>>b; int res=0;
                if(dp.find({a, b})!=dp.end()) { cout<<dp[{a, b}]<<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<<flush;
            }
            return 0;
        }

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 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 4 ms 6216 KB Time limit exceeded (wall clock)
9 Execution timed out 5 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 7468 KB Time limit exceeded (wall clock)
13 Execution timed out 13 ms 7496 KB Time limit exceeded (wall clock)
14 Execution timed out 14 ms 7852 KB Time limit exceeded (wall clock)
15 Execution timed out 19 ms 10316 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 37 ms 10816 KB Time limit exceeded (wall clock)
2 Execution timed out 34 ms 10572 KB Time limit exceeded (wall clock)
3 Execution timed out 35 ms 12588 KB Time limit exceeded (wall clock)
4 Execution timed out 19 ms 7992 KB Time limit exceeded (wall clock)
5 Execution timed out 21 ms 9452 KB Time limit exceeded (wall clock)
6 Execution timed out 29 ms 9336 KB Time limit exceeded (wall clock)
7 Execution timed out 42 ms 10468 KB Time limit exceeded (wall clock)
8 Execution timed out 45 ms 15056 KB Time limit exceeded (wall clock)
9 Execution timed out 74 ms 15992 KB Time limit exceeded (wall clock)
10 Execution timed out 75 ms 20540 KB Time limit exceeded (wall clock)
11 Execution timed out 116 ms 18368 KB Time limit exceeded (wall clock)
12 Execution timed out 103 ms 16904 KB Time limit exceeded (wall clock)
13 Execution timed out 107 ms 17952 KB Time limit exceeded (wall clock)
14 Execution timed out 108 ms 18028 KB Time limit exceeded (wall clock)
15 Execution timed out 92 ms 21240 KB Time limit exceeded (wall clock)
16 Execution timed out 100 ms 26532 KB Time limit exceeded (wall clock)
17 Execution timed out 89 ms 25320 KB Time limit exceeded (wall clock)