oj.uz

Submission #472932

# Submission time Handle Problem Language Result Execution time Memory
472932 2021-09-14T15:03:17 Z MohamedFaresNebili Regions (IOI09_regions) C++14
80 / 100
 8000 ms 36644 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, &r, &q);
            scanf("%d", &arr[1]); home[arr[1]].pb(1);
            for(int l=2;l<=n;l++) {
                int a, h; scanf("%d%d", &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", &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;
        }

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, &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", &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", &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", &a, &b); int res=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 11 ms 6216 KB Output is correct
5 Correct 14 ms 6216 KB Output is correct
6 Correct 23 ms 6336 KB Output is correct
7 Correct 31 ms 6332 KB Output is correct
8 Correct 42 ms 6476 KB Output is correct
9 Correct 54 ms 6900 KB Output is correct
10 Correct 97 ms 7332 KB Output is correct
11 Correct 170 ms 7660 KB Output is correct
12 Correct 144 ms 8136 KB Output is correct
13 Correct 209 ms 8384 KB Output is correct
14 Correct 289 ms 8596 KB Output is correct
15 Correct 286 ms 11252 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1681 ms 12672 KB Output is correct
2 Correct 1809 ms 12372 KB Output is correct
3 Correct 2835 ms 16556 KB Output is correct
4 Correct 366 ms 9680 KB Output is correct
5 Correct 408 ms 11736 KB Output is correct
6 Correct 630 ms 11384 KB Output is correct
7 Correct 1000 ms 11740 KB Output is correct
8 Correct 1643 ms 19268 KB Output is correct
9 Correct 2514 ms 24260 KB Output is correct
10 Correct 5153 ms 30708 KB Output is correct
11 Correct 4902 ms 30248 KB Output is correct
12 Correct 6432 ms 22060 KB Output is correct
13 Correct 7678 ms 24980 KB Output is correct
14 Execution timed out 8041 ms 24788 KB Time limit exceeded
15 Execution timed out 8010 ms 28644 KB Time limit exceeded
16 Execution timed out 8054 ms 35916 KB Time limit exceeded
17 Execution timed out 8058 ms 36644 KB Time limit exceeded