oj.uz

Submission #472943

# Submission time Handle Problem Language Result Execution time Memory
472943 2021-09-14T15:42:03 Z MohamedFaresNebili Regions (IOI09_regions) C++14
0 / 100
 129 ms 26568 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2")

        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";
            }
            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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 6088 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 6088 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 6088 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
9 Execution timed out 6 ms 6600 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 6728 KB Time limit exceeded (wall clock)
11 Execution timed out 11 ms 6952 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 7416 KB Time limit exceeded (wall clock)
13 Execution timed out 15 ms 7680 KB Time limit exceeded (wall clock)
14 Execution timed out 16 ms 7920 KB Time limit exceeded (wall clock)
15 Execution timed out 18 ms 10312 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 31 ms 10844 KB Time limit exceeded (wall clock)
2 Execution timed out 32 ms 10684 KB Time limit exceeded (wall clock)
3 Execution timed out 34 ms 12560 KB Time limit exceeded (wall clock)
4 Execution timed out 16 ms 8056 KB Time limit exceeded (wall clock)
5 Execution timed out 18 ms 9416 KB Time limit exceeded (wall clock)
6 Execution timed out 26 ms 9328 KB Time limit exceeded (wall clock)
7 Execution timed out 45 ms 10576 KB Time limit exceeded (wall clock)
8 Execution timed out 47 ms 15060 KB Time limit exceeded (wall clock)
9 Execution timed out 74 ms 16036 KB Time limit exceeded (wall clock)
10 Execution timed out 92 ms 20544 KB Time limit exceeded (wall clock)
11 Execution timed out 97 ms 18372 KB Time limit exceeded (wall clock)
12 Execution timed out 100 ms 16824 KB Time limit exceeded (wall clock)
13 Execution timed out 92 ms 17692 KB Time limit exceeded (wall clock)
14 Execution timed out 102 ms 17936 KB Time limit exceeded (wall clock)
15 Execution timed out 96 ms 21372 KB Time limit exceeded (wall clock)
16 Execution timed out 95 ms 26568 KB Time limit exceeded (wall clock)
17 Execution timed out 129 ms 25296 KB Time limit exceeded (wall clock)