| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 162759 |
2019-11-09T16:01:19 Z |
faremy |
Regions (IOI09_regions) |
C++14 |
|
3407 ms |
42504 KB |
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 2e5;
const int MAXR = 25e3;
const int SQRTN = 450;
std::vector<int> tree[MAXN];
int color[MAXN];
int ofColor[MAXR];
int dfsPre[MAXN], dfsPost[MAXN];
int order[MAXR], revOrder[MAXR];
int ofNewColor[MAXR];
long long onOfColor[MAXR];
std::vector<long long> ancestersOfColor[MAXR];
std::vector<int> intervalStarts[MAXR];
std::vector<int> intervalEnds[MAXR];
int analysetree(int node, int seen)
{
ofColor[color[node]]++;
dfsPre[node] = seen;
int subseen = 1;
for (int child : tree[node])
subseen += analysetree(child, seen + subseen);
dfsPost[node] = seen + subseen;
return (subseen + 1);
}
void recolor(int colors, int nodes)
{
for (int iColor = 0; iColor < colors; iColor++)
order[iColor] = iColor;
std::sort(order, order + colors, [](int a, int b) { return (ofColor[a] > ofColor[b]); });
for (int iColor = 0; iColor < colors; iColor++)
ofNewColor[iColor] = ofColor[order[iColor]];
for (int iColor = 0; iColor < colors; iColor++)
ofColor[iColor] = ofNewColor[iColor];
for (int iColor = 0; iColor < colors; iColor++)
revOrder[order[iColor]] = iColor;
for (int iNode = 0; iNode < nodes; iNode++)
color[iNode] = revOrder[color[iNode]];
}
void buildpartialanswers(int node, int colors, int bigColors)
{
if (color[node] < bigColors)
for (int iColor = 0; iColor < colors; iColor++)
ancestersOfColor[color[node]][iColor] += onOfColor[iColor];
else
for (int iColor = 0; iColor < bigColors; iColor++)
ancestersOfColor[color[node]][iColor] += onOfColor[iColor];
intervalStarts[color[node]].emplace_back(dfsPre[node]);
intervalEnds[color[node]].emplace_back(dfsPost[node]);
onOfColor[color[node]]++;
for (int child : tree[node])
buildpartialanswers(child, colors, bigColors);
onOfColor[color[node]]--;
}
long long countbyfusion(int ancCol, int descCol)
{
int iAnc = 0, maxEnd = -1;
int ancesterPairs = 0;
for (int iDesc = 0; iDesc < ofColor[descCol]; iDesc++)
{
for (; iAnc < ofColor[ancCol] && intervalStarts[ancCol][iAnc] < intervalStarts[descCol][iDesc]; iAnc++)
maxEnd = std::max(maxEnd, intervalEnds[ancCol][iAnc]);
ancesterPairs += (maxEnd > intervalEnds[descCol][iDesc]);
}
return ancesterPairs;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
int nodes, colors, queries;
std::cin >> nodes >> colors >> queries;
for (int iNode = 0; iNode < nodes; iNode++)
{
if (iNode > 0)
{
int parent; std::cin >> parent;
tree[parent - 1].emplace_back(iNode);
}
std::cin >> color[iNode];
color[iNode]--;
}
analysetree(0, 0);
recolor(colors, nodes);
int bigColors = 0;
while (bigColors < colors && ofColor[bigColors] > SQRTN)
bigColors++;
for (int iColor = 0; iColor < colors; iColor++)
{
if (iColor < bigColors)
ancestersOfColor[iColor].resize(colors, 0);
else
ancestersOfColor[iColor].resize(bigColors, 0);
}
buildpartialanswers(0, colors, bigColors);
for (int iQuery = 0; iQuery < queries; iQuery++)
{
int ancCol, descCol;
std::cin >> ancCol >> descCol;
ancCol = revOrder[ancCol - 1];
descCol = revOrder[descCol - 1];
if (descCol < bigColors || ancCol < bigColors)
std::cout << ancestersOfColor[descCol][ancCol] << std::endl;
else
std::cout << countbyfusion(ancCol, descCol) << std::endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6776 KB |
Output isn't correct |
| 2 |
Incorrect |
7 ms |
6776 KB |
Output isn't correct |
| 3 |
Incorrect |
9 ms |
6776 KB |
Output isn't correct |
| 4 |
Incorrect |
13 ms |
6776 KB |
Output isn't correct |
| 5 |
Incorrect |
17 ms |
6776 KB |
Output isn't correct |
| 6 |
Incorrect |
16 ms |
6904 KB |
Output isn't correct |
| 7 |
Incorrect |
36 ms |
6904 KB |
Output isn't correct |
| 8 |
Incorrect |
29 ms |
6952 KB |
Output isn't correct |
| 9 |
Incorrect |
55 ms |
7416 KB |
Output isn't correct |
| 10 |
Incorrect |
95 ms |
7316 KB |
Output isn't correct |
| 11 |
Incorrect |
78 ms |
7668 KB |
Output isn't correct |
| 12 |
Incorrect |
141 ms |
8216 KB |
Output isn't correct |
| 13 |
Incorrect |
182 ms |
7860 KB |
Output isn't correct |
| 14 |
Incorrect |
176 ms |
8444 KB |
Output isn't correct |
| 15 |
Incorrect |
230 ms |
10872 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
720 ms |
11532 KB |
Output isn't correct |
| 2 |
Incorrect |
1086 ms |
10364 KB |
Output isn't correct |
| 3 |
Incorrect |
1421 ms |
13224 KB |
Output isn't correct |
| 4 |
Incorrect |
284 ms |
8480 KB |
Output isn't correct |
| 5 |
Incorrect |
387 ms |
10104 KB |
Output isn't correct |
| 6 |
Incorrect |
808 ms |
16632 KB |
Output isn't correct |
| 7 |
Incorrect |
1022 ms |
13072 KB |
Output isn't correct |
| 8 |
Incorrect |
1194 ms |
31736 KB |
Output isn't correct |
| 9 |
Incorrect |
1379 ms |
16620 KB |
Output isn't correct |
| 10 |
Incorrect |
2324 ms |
42504 KB |
Output isn't correct |
| 11 |
Incorrect |
2233 ms |
16624 KB |
Output isn't correct |
| 12 |
Incorrect |
1381 ms |
18584 KB |
Output isn't correct |
| 13 |
Incorrect |
1644 ms |
18876 KB |
Output isn't correct |
| 14 |
Incorrect |
2778 ms |
25220 KB |
Output isn't correct |
| 15 |
Incorrect |
2677 ms |
23632 KB |
Output isn't correct |
| 16 |
Incorrect |
2890 ms |
28852 KB |
Output isn't correct |
| 17 |
Incorrect |
3407 ms |
33884 KB |
Output isn't correct |
