oj.uz

Submission #472954

# Submission time Handle Problem Language Result Execution time Memory
472954 2021-09-14T15:48:43 Z MohamedFaresNebili Regions (IOI09_regions) C++14
90 / 100
 8000 ms 38544 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#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:46:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |             scanf("%d%d%d", &n, &r, &q);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |             scanf("%d", &arr[1]); home[arr[1]].pb(1);
      |             ~~~~~^~~~~~~~~~~~~~~
regions.cpp:49:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |                 int a, h; scanf("%d%d", &a, &h); home[h].pb(l);
      |                           ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:54:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |                 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 6 ms 6216 KB Output is correct
4 Correct 9 ms 6216 KB Output is correct
5 Correct 14 ms 6232 KB Output is correct
6 Correct 29 ms 6308 KB Output is correct
7 Correct 37 ms 6372 KB Output is correct
8 Correct 41 ms 6464 KB Output is correct
9 Correct 71 ms 6976 KB Output is correct
10 Correct 120 ms 7208 KB Output is correct
11 Correct 158 ms 7564 KB Output is correct
12 Correct 187 ms 8328 KB Output is correct
13 Correct 260 ms 8356 KB Output is correct
14 Correct 354 ms 8656 KB Output is correct
15 Correct 281 ms 11252 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1825 ms 12700 KB Output is correct
2 Correct 1983 ms 12496 KB Output is correct
3 Correct 2646 ms 17056 KB Output is correct
4 Correct 308 ms 9744 KB Output is correct
5 Correct 509 ms 11524 KB Output is correct
6 Correct 757 ms 11396 KB Output is correct
7 Correct 1079 ms 11652 KB Output is correct
8 Correct 1517 ms 19148 KB Output is correct
9 Correct 3028 ms 24348 KB Output is correct
10 Correct 5764 ms 30680 KB Output is correct
11 Correct 5702 ms 30252 KB Output is correct
12 Correct 6229 ms 22140 KB Output is correct
13 Correct 6715 ms 24888 KB Output is correct
14 Execution timed out 8005 ms 25604 KB Time limit exceeded
15 Execution timed out 8053 ms 30300 KB Time limit exceeded
16 Correct 7507 ms 38544 KB Output is correct
17 Correct 7817 ms 36692 KB Output is correct