| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 162771 |
2019-11-09T16:48:25 Z |
faremy |
Regions (IOI09_regions) |
C++14 |
|
1756 ms |
131076 KB |
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 2e5;
const int MAXR = 25e3;
const int SQRTN = 2;
std::vector<int> tree[MAXN];
int color[MAXN];
int ofColor[MAXR];
int dfsPre[MAXN], dfsPost[MAXN];
int order[MAXR], revOrder[MAXR];
int ofNewColor[MAXR];
int onOfColor[MAXR];
std::vector<int> 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()
{
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] << '\n';
else
std::cout << countbyfusion(ancCol, descCol) << '\n';
std::cout << std::flush;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6776 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6776 KB |
Output is correct |
| 3 |
Correct |
10 ms |
6776 KB |
Output is correct |
| 4 |
Correct |
10 ms |
6904 KB |
Output is correct |
| 5 |
Correct |
18 ms |
6776 KB |
Output is correct |
| 6 |
Incorrect |
28 ms |
7160 KB |
Output isn't correct |
| 7 |
Correct |
24 ms |
6904 KB |
Output is correct |
| 8 |
Correct |
64 ms |
7160 KB |
Output is correct |
| 9 |
Correct |
81 ms |
7672 KB |
Output is correct |
| 10 |
Correct |
142 ms |
7928 KB |
Output is correct |
| 11 |
Correct |
151 ms |
7928 KB |
Output is correct |
| 12 |
Correct |
225 ms |
8952 KB |
Output is correct |
| 13 |
Correct |
221 ms |
8264 KB |
Output is correct |
| 14 |
Correct |
266 ms |
8560 KB |
Output is correct |
| 15 |
Correct |
318 ms |
11144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1077 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
1193 ms |
10396 KB |
Output is correct |
| 3 |
Correct |
1756 ms |
13536 KB |
Output is correct |
| 4 |
Correct |
1081 ms |
54612 KB |
Output is correct |
| 5 |
Incorrect |
1548 ms |
59796 KB |
Output isn't correct |
| 6 |
Runtime error |
176 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
195 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
219 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
320 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
299 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
351 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
351 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
390 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
369 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
351 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
344 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
331 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
