oj.uz

답안 #557732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557732 2022-05-06T01:14:13 Z HunterXD Regions (IOI09_regions) C++17
100 / 100
 5094 ms 31044 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<int,int> ii;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector <char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef pair<ll,ll> pl;
typedef double dou;
typedef vector<pl> vpl;
typedef unsigned long long ull;
typedef uint64_t i64;
typedef vector<ull> vull;

#define f first 
#define s second 
#define pb push_back 
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define ts to_string
#define lb lower_bound 
#define ub upper_bound
#define yes cout<<'Y'<<'E'<<'S'<<endl
#define no cout<<'N'<<'O'<<endl
#define nd "\n"

void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
 
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll mcm(ll a, ll b) {return (a * b) / gcd(a, b);}
bool prime(ll n) {for(int i=2; i<=sqrt(n); i++) if(n%i==0) return false; return true;}
struct compii{bool operator()(const ii &a, const ii &b){if(a.f==a.s)return a.s<b.s;return a.f>b.f;}};
bool comp(int a, int b) {return a>b;}
ll binpow(ll n, ll x){ll ans=1; while(x){if(x&1){ans*=n;}n*=n; x>>=1;} return ans;}

namespace operators {
template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2>& x){in >> x.first >> x.second;return in;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2> x){out << x.first << " " << x.second;return out;}
template<typename T1>istream& operator>>(istream& in, vector<T1>& x) {for (auto& i : x) in >> i;return in;}
template<typename T1>ostream& operator<<(ostream& out, vector<T1>& x) {for (auto& i : x) out << i << " ";return out;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, vector<pair <T1,T2>>& x) {for (auto& i : x) out << i.f << " "<<i.s;return out;}
template<typename T1, typename T2>istream& operator>>(istream& in, vector<pair <T1,T2>>& x) {for (auto& i : x) in >> i.f >>i.s;return in;}
}

using namespace operators;

int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};

const int pmod = 998244353;
const int mod = 1e9+7;
const ll inf=1e9;

ll sum(ll a, ll b){
  return (( (a+mod) %mod) + ((b+mod)%mod))%mod;
}

ll multi(ll a, ll b){
  return (((a+mod) %mod) * ((b+mod)%mod))%mod;
}

///

vector< vector<ll> > tree, res;
vector< vector<ll> > home, tour;
vector<ll> ini, fini;
vector<ll> h;

void dfs1(ll u, ll t, ll s){
  res[t][h[u]]+= s;
  if(h[u] == t) s++;
  for(auto v: tree[u]){
    dfs1(v, t, s);
  }
};

ll tiempo = 1;
void tourdfs(ll u){
  ini[u] = tiempo;
  tour[ h[u] ].pb(tiempo++);
  for(auto v: tree[u]){
    tourdfs(v);
  }
  fini[u] = tiempo;
  tour[ h[u] ].pb(tiempo++);
};


void solve(){
  ll n, r, q; 
  cin >> n >> r >> q;
  
  h.assign(n+1, 0);
  tree.assign(n+1, vector<ll>());
  home.assign(r+1, vector<ll>());
  res.assign(r+1, vector<ll>());
  tour.assign(r+1, vector<ll>());
  ini.assign(n+1, 0);
  fini = ini;


  ll s;
  cin >> h[1];
  home[ h[1] ].pb(1);

  for(ll i = 2; i <= n; i++){
    cin >> s >> h[i];
    tree[s].pb(i); 
    home[ h[i] ].pb(i);
  }

  ll nr = 0;

  while(nr*nr <= n) nr++;
  nr--;

  for(ll i = 1; i <= r; i++){
    if(home[i].size() > nr){
      res[i].assign(r+1, 0);
      dfs1(1, i, 0);
    }
  }

  tourdfs(1);

  vector<ll>::iterator it_ini, it_fini;

  ll r1, r2;
  for(ll i = 0; i < q; i++){
    cin >> r1 >> r2;
    if(home[r1].size() > nr){
      cout << res[r1][r2] << endl << flush;
    }
    else{
      ll res_temp = 0;
      for(auto v: home[r1]){
        it_ini = lower_bound(tour[r2].begin(), tour[r2].end(), ini[v]);
        it_fini = upper_bound(tour[r2].begin(), tour[r2].end(), fini[v]);

        if(it_ini != tour[r2].end()){
          if(*it_ini <= fini[v]){
            it_fini--;
            res_temp+= it_fini-it_ini+1;
          }
        }
      }
      res_temp/= 2;
      cout << res_temp << endl << flush;
    }
  }

}

int main (){
  setIO("");

  int t=1;
  while(t-->0) solve();
  return 0;
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:125:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  125 |     if(home[i].size() > nr){
      |        ~~~~~~~~~~~~~~~^~~~
regions.cpp:138:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  138 |     if(home[r1].size() > nr){
      |        ~~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void setIO(std::string)':
regions.cpp:34:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:34:128: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
      |                                                                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 14 ms 336 KB Output is correct
7 Correct 21 ms 336 KB Output is correct
8 Correct 33 ms 464 KB Output is correct
9 Correct 56 ms 976 KB Output is correct
10 Correct 73 ms 1104 KB Output is correct
11 Correct 77 ms 1616 KB Output is correct
12 Correct 155 ms 2256 KB Output is correct
13 Correct 189 ms 2024 KB Output is correct
14 Correct 306 ms 2896 KB Output is correct
15 Correct 319 ms 5712 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1878 ms 7180 KB Output is correct
2 Correct 2296 ms 6164 KB Output is correct
3 Correct 3441 ms 9384 KB Output is correct
4 Correct 281 ms 3196 KB Output is correct
5 Correct 356 ms 5044 KB Output is correct
6 Correct 578 ms 6856 KB Output is correct
7 Correct 1311 ms 8992 KB Output is correct
8 Correct 1194 ms 16748 KB Output is correct
9 Correct 2509 ms 15316 KB Output is correct
10 Correct 3263 ms 31044 KB Output is correct
11 Correct 5094 ms 17080 KB Output is correct
12 Correct 1435 ms 17624 KB Output is correct
13 Correct 2146 ms 17820 KB Output is correct
14 Correct 2808 ms 19836 KB Output is correct
15 Correct 3661 ms 22848 KB Output is correct
16 Correct 3440 ms 28120 KB Output is correct
17 Correct 3330 ms 28492 KB Output is correct