| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 299197 |
2020-09-14T14:42:30 Z |
mat_v |
Regions (IOI09_regions) |
C++14 |
|
8000 ms |
33528 KB |
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define pb push_back
#define maxn 200005
#define pair<int,int> pii
#define xx first
#define yy second
using namespace std;
typedef long long ll;
int n,r,q;
int dlt;
int niz[maxn];
bool veci[maxn];
int cale[maxn];
vector<int> graf[maxn];
vector<int> boja[maxn];
int disc[maxn];
int out[maxn];
int gde[maxn];
int slika[505];
int kolko[505][25005][2];
int tajm = 1;
void dfs(int x){
disc[x] = tajm;
for(auto c:graf[x]){
if(c == cale[x])continue;
tajm++;
dfs(c);
}
out[x] = tajm;
}
void color(int x, int last, int root, int idx){
kolko[root][niz[x]][idx]++;
for(auto c:graf[x]){
if(c == last)continue;
color(c,x,root,idx);
}
}
void color2(int x, int root, int idx){
if(x == 0)return;
kolko[root][niz[x]][idx]++;
color2(cale[x], root, idx);
}
bool cmp(int x, int y){
if(out[x] == out[y])return disc[x] > disc[y];
return out[x] < out[y];
}
int trg;
int subtr[maxn];
bool mark[maxn];
int val[maxn];
struct kurac{
int l;
int op;
int idx;
int pre;
};
bool cmpkurac(kurac a, kurac b){
if(a.l != b.l)return a.l < b.l;
if(a.l == b.l){
if(a.op == 0)return 1;
if(b.op == 0)return 0;
return a.pre > b.pre;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> n >> r >> q;
while(dlt * dlt < n)dlt++;
ff(i,1,n){
if(i == 1){
cin >> niz[i];
boja[niz[i]].pb(i);
continue;
}
cin >> cale[i];
cin >> niz[i];
graf[i].pb(cale[i]);
boja[niz[i]].pb(i);
graf[cale[i]].pb(i);
}
dfs(1);
int br = 1;
ff(i,1,r){
int sta = boja[i].size();
if(sta >= dlt)veci[i] = 1;
if(veci[i]){
slika[br] = i;
gde[i] = br;
//cout << i << ": \n";
for(auto c:boja[i]){
//cout << c << " ";
color(c,cale[c],br,0);
color2(cale[c],br,1);
kolko[br][i][0]--;
}
//cout << kolko[br][1][0] << "\n";
//cout << "\n";
br++;
continue;
}
sort(boja[i].begin(), boja[i].end(), cmp);
vector<kurac> all;
for(auto c:boja[i]){
//cout << c << " " << disc[c] << " " << out[c] << "\n";
all.pb({disc[c], 0, c, 0});
all.pb({out[c], 1, c, disc[c]});
}
sort(all.begin(), all.end(), cmpkurac);
int sad = 0;
for(auto c:all){
if(c.op == 0)sad++;
else{
val[c.idx] = sad;
sad--;
}
}
//return 0;
}
while(q--){
int r1,r2;
cin >> r1 >> r2;
cout << endl;
if(veci[r1] || veci[r2]){
//cout << "AAAA\n";
if(veci[r1]){
cout << kolko[gde[r1]][r2][0] << endl;
}
else{
cout << kolko[gde[r2]][r1][1] << endl;
}
}
else{
//cout << "BBBB\n";
int p1 = 0;
int p2 = 0;
int ans = 0;
while(p1 < boja[r1].size() && p2 < boja[r2].size()){
int prvi = boja[r1][p1];
int drugi = boja[r2][p2];
//cout << prvi << " " << drugi << "\n";
//cout << disc[prvi] << " " << out[prvi] << " " << out[drugi] << "\n";
if(out[drugi] > out[prvi]){
p1++;
}
else{
if(out[drugi] <= out[prvi]){
if(disc[drugi] > disc[prvi]){
ans += val[prvi];
p2++;
}
else{
p1++;
}
}
}
}
cout << ans << endl;
}
}
return 0;
}
Compilation message
regions.cpp:5:9: warning: ISO C++11 requires whitespace after the macro name
5 | #define pair<int,int> pii
| ^~~~
regions.cpp: In function 'int main()':
regions.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
regions.cpp:91:5: note: in expansion of macro 'ff'
91 | ff(i,1,n){
| ^~
regions.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
regions.cpp:105:5: note: in expansion of macro 'ff'
105 | ff(i,1,r){
| ^~
regions.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | while(p1 < boja[r1].size() && p2 < boja[r2].size()){
| ~~~^~~~~~~~~~~~~~~~~
regions.cpp:162:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | while(p1 < boja[r1].size() && p2 < boja[r2].size()){
| ~~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'bool cmpkurac(kurac, kurac)':
regions.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
83 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 3 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
| 4 |
Incorrect |
11 ms |
9728 KB |
Output isn't correct |
| 5 |
Incorrect |
15 ms |
9728 KB |
Output isn't correct |
| 6 |
Correct |
29 ms |
9856 KB |
Output is correct |
| 7 |
Incorrect |
34 ms |
9856 KB |
Output isn't correct |
| 8 |
Incorrect |
34 ms |
9856 KB |
Output isn't correct |
| 9 |
Correct |
53 ms |
10240 KB |
Output is correct |
| 10 |
Incorrect |
92 ms |
10368 KB |
Output isn't correct |
| 11 |
Incorrect |
110 ms |
10624 KB |
Output isn't correct |
| 12 |
Incorrect |
133 ms |
11008 KB |
Output isn't correct |
| 13 |
Incorrect |
153 ms |
11136 KB |
Output isn't correct |
| 14 |
Incorrect |
155 ms |
11520 KB |
Output isn't correct |
| 15 |
Correct |
264 ms |
14592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8045 ms |
15188 KB |
Time limit exceeded |
| 2 |
Incorrect |
2546 ms |
14712 KB |
Output isn't correct |
| 3 |
Execution timed out |
8055 ms |
17144 KB |
Time limit exceeded |
| 4 |
Incorrect |
233 ms |
11648 KB |
Output isn't correct |
| 5 |
Incorrect |
389 ms |
12672 KB |
Output isn't correct |
| 6 |
Incorrect |
4220 ms |
16644 KB |
Output isn't correct |
| 7 |
Incorrect |
3455 ms |
18408 KB |
Output isn't correct |
| 8 |
Execution timed out |
8066 ms |
21876 KB |
Time limit exceeded |
| 9 |
Incorrect |
2302 ms |
19320 KB |
Output isn't correct |
| 10 |
Execution timed out |
8096 ms |
28420 KB |
Time limit exceeded |
| 11 |
Incorrect |
1812 ms |
22004 KB |
Output isn't correct |
| 12 |
Execution timed out |
8073 ms |
21172 KB |
Time limit exceeded |
| 13 |
Execution timed out |
8064 ms |
22040 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8036 ms |
22368 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8073 ms |
26104 KB |
Time limit exceeded |
| 16 |
Execution timed out |
8064 ms |
33528 KB |
Time limit exceeded |
| 17 |
Execution timed out |
8045 ms |
32272 KB |
Time limit exceeded |
