oj.uz

Submission #472975

# Submission time Handle Problem Language Result Execution time Memory
472975 2021-09-14T16:38:30 Z MohamedFaresNebili Regions (IOI09_regions) C++14
100 / 100
 5232 ms 52280 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("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]; int cnt[25005];
        vector<int>adj[200005], se[25005]; vector<int>home[25005]; map<ii, int>dp; vector<ii>trav[25005];
        void dfs(int v, int p) {
            cnt[arr[v]]++; tin[v]=++timer;
            se[arr[v]].pb(timer); trav[arr[v]].pb({tin[v], cnt[arr[v]]});
            for(auto u:adj[v]) {
                if(u==p) continue;
                dfs(u, v);
            }
            out[v]=++timer; cnt[arr[v]]--;
            trav[arr[v]].pb({out[v], cnt[arr[v]]});
        }

        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; bool swp=false;
                if(dp.find({a, b})!=dp.end()) { cout<<dp[{a, b}]<<"\n"<<flush; continue; }
                if(se[a].size()>se[b].size()) swap(a, b), swp=true;
                for(auto u:home[a]) {
                    int l=tin[u], r=out[u];
                    if(swp) {
                        auto it=lb(all(trav[b]), mp(l, INT_MAX));
                        if(it!=trav[b].begin()) {
                            it--; res+=it->second;
                        }
                    }
                    else res+=lb(all(se[b]), r)-lb(all(se[b]), l);
                }
                if(swp) swap(a, b);
                dp[{a, b}]=res; cout<<res<<"\n"<<flush;
            }
            return 0;
        }

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |             scanf("%d%d%d", &n, &r, &q);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |             scanf("%d", &arr[1]); home[arr[1]].pb(1);
      |             ~~~~~^~~~~~~~~~~~~~~
regions.cpp:51:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |                 int a, h; scanf("%d%d", &a, &h); home[h].pb(l);
      |                           ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:56:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |                 int a, b; scanf("%d%d", &a, &b); int res=0; bool swp=false;
      |                           ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6728 KB Output is correct
2 Correct 4 ms 6728 KB Output is correct
3 Correct 7 ms 6728 KB Output is correct
4 Correct 10 ms 6728 KB Output is correct
5 Correct 12 ms 6864 KB Output is correct
6 Correct 16 ms 7016 KB Output is correct
7 Correct 34 ms 7008 KB Output is correct
8 Correct 56 ms 7120 KB Output is correct
9 Correct 35 ms 7924 KB Output is correct
10 Correct 117 ms 7996 KB Output is correct
11 Correct 153 ms 8568 KB Output is correct
12 Correct 199 ms 9400 KB Output is correct
13 Correct 245 ms 9528 KB Output is correct
14 Correct 301 ms 10028 KB Output is correct
15 Correct 351 ms 14880 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1298 ms 15328 KB Output is correct
2 Correct 1408 ms 14744 KB Output is correct
3 Correct 2494 ms 20716 KB Output is correct
4 Correct 311 ms 11200 KB Output is correct
5 Correct 412 ms 14216 KB Output is correct
6 Correct 619 ms 13372 KB Output is correct
7 Correct 1037 ms 14620 KB Output is correct
8 Correct 1110 ms 25000 KB Output is correct
9 Correct 2224 ms 29784 KB Output is correct
10 Correct 4174 ms 39052 KB Output is correct
11 Correct 5232 ms 35752 KB Output is correct
12 Correct 1756 ms 26640 KB Output is correct
13 Correct 2338 ms 30344 KB Output is correct
14 Correct 2943 ms 31836 KB Output is correct
15 Correct 3898 ms 40868 KB Output is correct
16 Correct 3900 ms 52280 KB Output is correct
17 Correct 3627 ms 49524 KB Output is correct