| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 557727 |
2022-05-06T01:05:57 Z |
HunterXD |
Regions (IOI09_regions) |
C++17 |
|
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);}}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
