oj.uz

Submission #472928

# Submission time Handle Problem Language Result Execution time Memory
472928 2021-09-14T14:55:46 Z MohamedFaresNebili Regions (IOI09_regions) C++14
0 / 100
 120 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]; 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}]<<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<<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
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 4 ms 6088 KB Time limit exceeded (wall clock)
3 Execution timed out 4 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 5 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 10 ms 6984 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 7496 KB Time limit exceeded (wall clock)
13 Execution timed out 13 ms 7496 KB Time limit exceeded (wall clock)
14 Execution timed out 15 ms 7892 KB Time limit exceeded (wall clock)
15 Execution timed out 19 ms 10256 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 30 ms 10872 KB Time limit exceeded (wall clock)
2 Execution timed out 33 ms 10688 KB Time limit exceeded (wall clock)
3 Execution timed out 35 ms 12608 KB Time limit exceeded (wall clock)
4 Execution timed out 20 ms 8008 KB Time limit exceeded (wall clock)
5 Execution timed out 19 ms 9416 KB Time limit exceeded (wall clock)
6 Execution timed out 29 ms 9324 KB Time limit exceeded (wall clock)
7 Execution timed out 37 ms 10524 KB Time limit exceeded (wall clock)
8 Execution timed out 45 ms 15040 KB Time limit exceeded (wall clock)
9 Execution timed out 101 ms 15936 KB Time limit exceeded (wall clock)
10 Execution timed out 77 ms 20484 KB Time limit exceeded (wall clock)
11 Execution timed out 100 ms 18356 KB Time limit exceeded (wall clock)
12 Execution timed out 113 ms 16908 KB Time limit exceeded (wall clock)
13 Execution timed out 91 ms 17668 KB Time limit exceeded (wall clock)
14 Execution timed out 120 ms 18160 KB Time limit exceeded (wall clock)
15 Execution timed out 104 ms 21184 KB Time limit exceeded (wall clock)
16 Execution timed out 99 ms 26560 KB Time limit exceeded (wall clock)
17 Execution timed out 94 ms 25280 KB Time limit exceeded (wall clock)