oj.uz

Submission #472917

# Submission time Handle Problem Language Result Execution time Memory
472917 2021-09-14T14:33:59 Z MohamedFaresNebili Regions (IOI09_regions) C++14
80 / 100
 8000 ms 36604 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 6 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 8 ms 6088 KB Output is correct
4 Correct 9 ms 6224 KB Output is correct
5 Correct 13 ms 6244 KB Output is correct
6 Correct 23 ms 6296 KB Output is correct
7 Correct 47 ms 6336 KB Output is correct
8 Correct 38 ms 6464 KB Output is correct
9 Correct 59 ms 6976 KB Output is correct
10 Correct 119 ms 7188 KB Output is correct
11 Correct 149 ms 7744 KB Output is correct
12 Correct 196 ms 8220 KB Output is correct
13 Correct 261 ms 8332 KB Output is correct
14 Correct 334 ms 8576 KB Output is correct
15 Correct 325 ms 11292 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1782 ms 12592 KB Output is correct
2 Correct 1621 ms 12564 KB Output is correct
3 Correct 2433 ms 16608 KB Output is correct
4 Correct 334 ms 9652 KB Output is correct
5 Correct 516 ms 11652 KB Output is correct
6 Correct 687 ms 11640 KB Output is correct
7 Correct 1030 ms 11732 KB Output is correct
8 Correct 1159 ms 19212 KB Output is correct
9 Correct 3114 ms 24264 KB Output is correct
10 Correct 4858 ms 30784 KB Output is correct
11 Correct 5672 ms 30344 KB Output is correct
12 Correct 6675 ms 22216 KB Output is correct
13 Correct 7711 ms 24888 KB Output is correct
14 Execution timed out 8009 ms 24752 KB Time limit exceeded
15 Execution timed out 8015 ms 29008 KB Time limit exceeded
16 Execution timed out 8029 ms 36356 KB Time limit exceeded
17 Execution timed out 8070 ms 36604 KB Time limit exceeded