| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 162772 |
2019-11-09T16:51:50 Z |
faremy |
Regions (IOI09_regions) |
C++14 |
|
8000 ms |
32240 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];
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 |
Incorrect |
9 ms |
6776 KB |
Output isn't correct |
| 2 |
Incorrect |
8 ms |
6776 KB |
Output isn't correct |
| 3 |
Incorrect |
11 ms |
6780 KB |
Output isn't correct |
| 4 |
Incorrect |
10 ms |
6904 KB |
Output isn't correct |
| 5 |
Incorrect |
15 ms |
6776 KB |
Output isn't correct |
| 6 |
Incorrect |
29 ms |
6904 KB |
Output isn't correct |
| 7 |
Incorrect |
27 ms |
6776 KB |
Output isn't correct |
| 8 |
Incorrect |
57 ms |
6908 KB |
Output isn't correct |
| 9 |
Incorrect |
46 ms |
7368 KB |
Output isn't correct |
| 10 |
Incorrect |
76 ms |
7464 KB |
Output isn't correct |
| 11 |
Incorrect |
101 ms |
7544 KB |
Output isn't correct |
| 12 |
Incorrect |
128 ms |
8056 KB |
Output isn't correct |
| 13 |
Incorrect |
140 ms |
7800 KB |
Output isn't correct |
| 14 |
Incorrect |
197 ms |
8292 KB |
Output isn't correct |
| 15 |
Incorrect |
197 ms |
10872 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1042 ms |
11472 KB |
Output isn't correct |
| 2 |
Incorrect |
1232 ms |
10232 KB |
Output isn't correct |
| 3 |
Incorrect |
1802 ms |
13284 KB |
Output isn't correct |
| 4 |
Incorrect |
262 ms |
8524 KB |
Output isn't correct |
| 5 |
Incorrect |
426 ms |
10104 KB |
Output isn't correct |
| 6 |
Incorrect |
1911 ms |
13224 KB |
Output isn't correct |
| 7 |
Incorrect |
1509 ms |
12160 KB |
Output isn't correct |
| 8 |
Incorrect |
3993 ms |
24020 KB |
Output isn't correct |
| 9 |
Incorrect |
1798 ms |
16428 KB |
Output isn't correct |
| 10 |
Incorrect |
6100 ms |
32240 KB |
Output isn't correct |
| 11 |
Incorrect |
2984 ms |
16400 KB |
Output isn't correct |
| 12 |
Incorrect |
4309 ms |
18528 KB |
Output isn't correct |
| 13 |
Incorrect |
4673 ms |
18556 KB |
Output isn't correct |
| 14 |
Execution timed out |
8016 ms |
21572 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8009 ms |
23368 KB |
Time limit exceeded |
| 16 |
Incorrect |
7450 ms |
28624 KB |
Output isn't correct |
| 17 |
Execution timed out |
8042 ms |
30392 KB |
Time limit exceeded |
