oj.uz

Submission #472931

# Submission time Handle Problem Language Result Execution time Memory
472931 2021-09-14T15:02:06 Z MohamedFaresNebili Regions (IOI09_regions) C++14
80 / 100
 8000 ms 36020 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}]<<"\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;
        }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6088 KB Output is correct
2 Correct 5 ms 6088 KB Output is correct
3 Correct 7 ms 6088 KB Output is correct
4 Correct 10 ms 6216 KB Output is correct
5 Correct 14 ms 6216 KB Output is correct
6 Correct 32 ms 6340 KB Output is correct
7 Correct 44 ms 6336 KB Output is correct
8 Correct 50 ms 6504 KB Output is correct
9 Correct 47 ms 6896 KB Output is correct
10 Correct 94 ms 7188 KB Output is correct
11 Correct 139 ms 7528 KB Output is correct
12 Correct 194 ms 8208 KB Output is correct
13 Correct 220 ms 8264 KB Output is correct
14 Correct 342 ms 8612 KB Output is correct
15 Correct 237 ms 11360 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1705 ms 12568 KB Output is correct
2 Correct 1961 ms 12400 KB Output is correct
3 Correct 2669 ms 16704 KB Output is correct
4 Correct 365 ms 9780 KB Output is correct
5 Correct 437 ms 11748 KB Output is correct
6 Correct 802 ms 11484 KB Output is correct
7 Correct 859 ms 11780 KB Output is correct
8 Correct 1559 ms 19224 KB Output is correct
9 Correct 2954 ms 24308 KB Output is correct
10 Correct 4853 ms 30660 KB Output is correct
11 Correct 5258 ms 30304 KB Output is correct
12 Correct 6643 ms 22368 KB Output is correct
13 Correct 7646 ms 24940 KB Output is correct
14 Execution timed out 8041 ms 24884 KB Time limit exceeded
15 Execution timed out 8057 ms 29192 KB Time limit exceeded
16 Execution timed out 8055 ms 35964 KB Time limit exceeded
17 Execution timed out 8042 ms 36020 KB Time limit exceeded