oj.uz

Submission #472929

# Submission time Handle Problem Language Result Execution time Memory
472929 2021-09-14T14:57:48 Z MohamedFaresNebili Regions (IOI09_regions) C++14
0 / 100
 130 ms 26452 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 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 8 ms 6728 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 6996 KB Time limit exceeded (wall clock)
12 Execution timed out 14 ms 7496 KB Time limit exceeded (wall clock)
13 Execution timed out 14 ms 7496 KB Time limit exceeded (wall clock)
14 Execution timed out 18 ms 7880 KB Time limit exceeded (wall clock)
15 Execution timed out 19 ms 10304 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 31 ms 10912 KB Time limit exceeded (wall clock)
2 Execution timed out 35 ms 10620 KB Time limit exceeded (wall clock)
3 Execution timed out 36 ms 12608 KB Time limit exceeded (wall clock)
4 Execution timed out 16 ms 8008 KB Time limit exceeded (wall clock)
5 Execution timed out 23 ms 9436 KB Time limit exceeded (wall clock)
6 Execution timed out 28 ms 9372 KB Time limit exceeded (wall clock)
7 Execution timed out 36 ms 10536 KB Time limit exceeded (wall clock)
8 Execution timed out 46 ms 15040 KB Time limit exceeded (wall clock)
9 Execution timed out 87 ms 16024 KB Time limit exceeded (wall clock)
10 Execution timed out 78 ms 20580 KB Time limit exceeded (wall clock)
11 Execution timed out 103 ms 18388 KB Time limit exceeded (wall clock)
12 Execution timed out 125 ms 16968 KB Time limit exceeded (wall clock)
13 Execution timed out 99 ms 17608 KB Time limit exceeded (wall clock)
14 Execution timed out 116 ms 17936 KB Time limit exceeded (wall clock)
15 Execution timed out 101 ms 21236 KB Time limit exceeded (wall clock)
16 Execution timed out 99 ms 26452 KB Time limit exceeded (wall clock)
17 Execution timed out 130 ms 25368 KB Time limit exceeded (wall clock)