oj.uz

Submission #472916

# Submission time Handle Problem Language Result Execution time Memory
472916 2021-09-14T14:27:57 Z MohamedFaresNebili Regions (IOI09_regions) C++14
65 / 100
 8000 ms 26560 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];
        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;
                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;
                }
                cout<<res<<"\n"<<flush;
            }
            return 0;
        }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 7 ms 6088 KB Output is correct
4 Correct 10 ms 6172 KB Output is correct
5 Correct 13 ms 6216 KB Output is correct
6 Correct 27 ms 6216 KB Output is correct
7 Correct 28 ms 6216 KB Output is correct
8 Correct 51 ms 6216 KB Output is correct
9 Correct 62 ms 6708 KB Output is correct
10 Correct 79 ms 6728 KB Output is correct
11 Correct 146 ms 7040 KB Output is correct
12 Correct 173 ms 7516 KB Output is correct
13 Correct 170 ms 7496 KB Output is correct
14 Correct 356 ms 7944 KB Output is correct
15 Correct 276 ms 10340 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8052 ms 10824 KB Time limit exceeded
2 Execution timed out 8018 ms 10688 KB Time limit exceeded
3 Execution timed out 8038 ms 12536 KB Time limit exceeded
4 Correct 285 ms 8100 KB Output is correct
5 Correct 390 ms 9492 KB Output is correct
6 Correct 1443 ms 9400 KB Output is correct
7 Correct 1787 ms 10548 KB Output is correct
8 Correct 1334 ms 15148 KB Output is correct
9 Correct 2556 ms 16044 KB Output is correct
10 Correct 4760 ms 20548 KB Output is correct
11 Correct 4479 ms 18488 KB Output is correct
12 Correct 7045 ms 16948 KB Output is correct
13 Correct 7590 ms 17716 KB Output is correct
14 Execution timed out 8077 ms 17952 KB Time limit exceeded
15 Execution timed out 8058 ms 21236 KB Time limit exceeded
16 Execution timed out 8031 ms 26560 KB Time limit exceeded
17 Execution timed out 8016 ms 25280 KB Time limit exceeded