oj.uz

답안 #557727

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557727 2022-05-06T01:05:57 Z HunterXD Regions (IOI09_regions) C++17
90 / 100
 8000 ms 81636 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--;
  nr/= 3;

  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;
    }
    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;
    }
    cout.flush();
  }

}

int main (){
  setIO("");

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

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:126:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  126 |     if(home[i].size() > nr){
      |        ~~~~~~~~~~~~~~~^~~~
regions.cpp:139:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  139 |     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 4 ms 208 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 16 ms 336 KB Output is correct
7 Correct 26 ms 464 KB Output is correct
8 Correct 31 ms 464 KB Output is correct
9 Correct 42 ms 976 KB Output is correct
10 Correct 58 ms 1104 KB Output is correct
11 Correct 179 ms 1832 KB Output is correct
12 Correct 193 ms 2456 KB Output is correct
13 Correct 352 ms 2524 KB Output is correct
14 Correct 282 ms 3052 KB Output is correct
15 Correct 265 ms 5932 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 738 ms 7388 KB Output is correct
2 Correct 996 ms 6300 KB Output is correct
3 Correct 1199 ms 9672 KB Output is correct
4 Correct 278 ms 4760 KB Output is correct
5 Correct 363 ms 7004 KB Output is correct
6 Correct 494 ms 6968 KB Output is correct
7 Correct 960 ms 11152 KB Output is correct
8 Correct 1155 ms 19732 KB Output is correct
9 Correct 6232 ms 50576 KB Output is correct
10 Correct 3255 ms 79972 KB Output is correct
11 Correct 7647 ms 76036 KB Output is correct
12 Execution timed out 8084 ms 43096 KB Time limit exceeded
13 Correct 7786 ms 55600 KB Output is correct
14 Execution timed out 8068 ms 54400 KB Time limit exceeded
15 Correct 5650 ms 81636 KB Output is correct
16 Correct 3716 ms 77060 KB Output is correct
17 Correct 3777 ms 67700 KB Output is correct