oj.uz

Submission #472918

# Submission time Handle Problem Language Result Execution time Memory
472918 2021-09-14T14:38:40 Z MohamedFaresNebili Regions (IOI09_regions) C++14
0 / 100
 11 ms 12360 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\n", n); scanf("%d\n", r); scanf("%d\n", q);
            scanf("%d\n", arr[1]); home[arr[1]].pb(1);
            for(int l=2;l<=n;l++) {
                int a, h; scanf("%d\n", a); scanf("%d\n", h); home[h].pb(l);
                adj[a].pb(l); adj[l].pb(a); arr[l]=h;
            }
            dfs(1, 1);
            while(q--) {
                int a, b; cin>>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:21: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
   44 |             scanf("%d\n", n); scanf("%d\n", r); scanf("%d\n", q);
      |                    ~^     ~
      |                     |     |
      |                     int*  int
regions.cpp:44:39: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
   44 |             scanf("%d\n", n); scanf("%d\n", r); scanf("%d\n", q);
      |                                      ~^     ~
      |                                       |     |
      |                                       int*  int
regions.cpp:44:57: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
   44 |             scanf("%d\n", n); scanf("%d\n", r); scanf("%d\n", q);
      |                                                        ~^     ~
      |                                                         |     |
      |                                                         int*  int
regions.cpp:45:21: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
   45 |             scanf("%d\n", arr[1]); home[arr[1]].pb(1);
      |                    ~^     ~~~~~~
      |                     |          |
      |                     int*       int
regions.cpp:47:35: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
   47 |                 int a, h; scanf("%d\n", a); scanf("%d\n", h); home[h].pb(l);
      |                                  ~^     ~
      |                                   |     |
      |                                   int*  int
regions.cpp:47:53: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
   47 |                 int a, h; scanf("%d\n", a); scanf("%d\n", h); home[h].pb(l);
      |                                                    ~^     ~
      |                                                     |     |
      |                                                     int*  int
regions.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |             scanf("%d\n", n); scanf("%d\n", r); scanf("%d\n", q);
      |             ~~~~~^~~~~~~~~~~
regions.cpp:44:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |             scanf("%d\n", n); scanf("%d\n", r); scanf("%d\n", q);
      |                               ~~~~~^~~~~~~~~~~
regions.cpp:44:54: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |             scanf("%d\n", n); scanf("%d\n", r); scanf("%d\n", 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\n", 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\n", a); scanf("%d\n", h); home[h].pb(l);
      |                           ~~~~~^~~~~~~~~~~
regions.cpp:47:50: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |                 int a, h; scanf("%d\n", a); scanf("%d\n", h); home[h].pb(l);
      |                                             ~~~~~^~~~~~~~~~~
regions.cpp:47:24: warning: 'h' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |                 int a, h; scanf("%d\n", a); scanf("%d\n", h); home[h].pb(l);
      |                        ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 12244 KB Execution killed with signal 11
2 Runtime error 10 ms 12360 KB Execution killed with signal 11
3 Runtime error 9 ms 12360 KB Execution killed with signal 11
4 Runtime error 10 ms 12232 KB Execution killed with signal 11
5 Runtime error 10 ms 12360 KB Execution killed with signal 11
6 Runtime error 9 ms 12360 KB Execution killed with signal 11
7 Runtime error 10 ms 12360 KB Execution killed with signal 11
8 Runtime error 10 ms 12360 KB Execution killed with signal 11
9 Runtime error 11 ms 12360 KB Execution killed with signal 11
10 Runtime error 10 ms 12360 KB Execution killed with signal 11
11 Runtime error 10 ms 12360 KB Execution killed with signal 11
12 Runtime error 9 ms 12360 KB Execution killed with signal 11
13 Runtime error 9 ms 12360 KB Execution killed with signal 11
14 Runtime error 9 ms 12360 KB Execution killed with signal 11
15 Runtime error 10 ms 12288 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 12336 KB Execution killed with signal 11
2 Runtime error 9 ms 12360 KB Execution killed with signal 11
3 Runtime error 10 ms 12360 KB Execution killed with signal 11
4 Runtime error 10 ms 12360 KB Execution killed with signal 11
5 Runtime error 10 ms 12360 KB Execution killed with signal 11
6 Runtime error 11 ms 12360 KB Execution killed with signal 11
7 Runtime error 10 ms 12360 KB Execution killed with signal 11
8 Runtime error 10 ms 12360 KB Execution killed with signal 11
9 Runtime error 9 ms 12360 KB Execution killed with signal 11
10 Runtime error 10 ms 12360 KB Execution killed with signal 11
11 Runtime error 10 ms 12360 KB Execution killed with signal 11
12 Runtime error 10 ms 12360 KB Execution killed with signal 11
13 Runtime error 9 ms 12360 KB Execution killed with signal 11
14 Runtime error 9 ms 12360 KB Execution killed with signal 11
15 Runtime error 10 ms 12260 KB Execution killed with signal 11
16 Runtime error 10 ms 12360 KB Execution killed with signal 11
17 Runtime error 10 ms 12360 KB Execution killed with signal 11