#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int MAX_N = 200000;
vector<int> graph[MAX_N];
vector<pair<int, int> > components[MAX_N];
struct CompEdge {
int a, b, timestamp1, timestamp2;
};
vector<CompEdge> edges;
int currComp[MAX_N];
int sizeComp[MAX_N];
int poz[MAX_N];
void dfs(int nod, int oldComp, int newComp, int timestamp) {
sizeComp[oldComp]--;
sizeComp[newComp]++;
currComp[nod] = newComp;
components[nod].push_back(make_pair(newComp, timestamp));
for(auto it: graph[nod])
if(currComp[it] == oldComp)
dfs(it, oldComp, newComp, timestamp);
}
void mergeComps(int a, int b, int timestamp) {
if(sizeComp[currComp[a]] < sizeComp[currComp[b]])
swap(a, b);
dfs(b, currComp[b], currComp[a], timestamp);
}
void dfs2(int nod, int oldComp, int newComp, int timestamp) {
for(auto it: components[nod])
edges.push_back({it.first, newComp, it.second, timestamp});
sizeComp[oldComp]--;
sizeComp[newComp]++;
currComp[nod] = newComp;
for(auto it: graph[nod])
if(currComp[it] == oldComp)
dfs2(it, oldComp, newComp, timestamp);
}
void mergeComps2(int a, int b, int timestamp) {
if(sizeComp[currComp[a]] < sizeComp[currComp[b]])
swap(a, b);
dfs2(b, currComp[b], currComp[a], timestamp);
}
void dfs3(int nod, int oldComp, int newComp) {
sizeComp[oldComp]--;
sizeComp[newComp]++;
currComp[nod] = newComp;
for(auto it: graph[nod])
if(currComp[it] == oldComp)
dfs3(it, oldComp, newComp);
}
void mergeComps3(int a, int b) {
if(sizeComp[currComp[a]] < sizeComp[currComp[b]])
swap(a, b);
dfs3(b, currComp[b], currComp[a]);
}
int pozQ[MAX_N];
std::vector<int> LQ;
bool cmp(int a, int b) {
return LQ[a] > LQ[b];
}
unordered_map<int, int> firstTime[MAX_N];
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int Q = S.size();
LQ = L;
std::vector<int> rez(Q);
for(int i = 0; i < Q; ++i)
pozQ[i] = i;
std::sort(pozQ, pozQ + Q, cmp);
for(int i = 0; i < X.size(); ++i) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; ++i) {
currComp[i] = i;
sizeComp[i] = 1;
}
for(int i = 0; i < N; ++i) {
components[i].push_back(make_pair(i, 0));
for(auto it: graph[i])
if(it < i && currComp[i] != currComp[it])
mergeComps(it, i, i);
}
for(int i = 0; i < N; ++i) {
currComp[i] = i;
sizeComp[i] = 1;
}
for(int i = N - 1; i >= 0; --i) {
for(auto it: components[i])
edges.push_back({it.first, i, it.second, i});
for(auto it: graph[i])
if(it > i && currComp[it] != currComp[i]) {
mergeComps2(it, i, i);
}
}
for(int i = 0; i < N; ++i) {
currComp[i] = i;
sizeComp[i] = 1;
}
int lastup = N - 1;
int lastE = 0;
for(int i = 0; i < Q; ++i) {
int l, r, s, e;
l = L[pozQ[i]];
r = R[pozQ[i]];
s = S[pozQ[i]];
e = E[pozQ[i]];
while(lastup >= l) {
for(auto it: graph[lastup])
if(lastup < it && currComp[lastup] != currComp[it])
mergeComps3(it, lastup);
--lastup;
}
while(lastE < edges.size() && edges[lastE].timestamp2 >= l) {
if(edges[lastE].timestamp2 <= edges[lastE].timestamp2) {
int a = edges[lastE].a, b = edges[lastE].b, ts = edges[lastE].timestamp1;
firstTime[a][b] = min(firstTime[a][b], ts - MAX_N);
}
++lastE;
}
int compS, compE = currComp[s];
int stB = 0, drB = components[e].size();
while(drB - stB > 1) {
int mid = (stB + drB) / 2;
if(components[e][mid].second <= r)
stB = mid;
else
drB = mid;
}
compS = components[e][stB].first;
if(firstTime[compS][compE] + MAX_N <= r)
rez[pozQ[i]] = true;
else
rez[pozQ[i]] = false;
}
return rez;
}
Compilation message
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < X.size(); ++i) {
~~^~~~~~~~~~
werewolf.cpp:145:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(lastE < edges.size() && edges[lastE].timestamp2 >= l) {
~~~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
20728 KB |
Output is correct |
2 |
Correct |
23 ms |
20852 KB |
Output is correct |
3 |
Correct |
21 ms |
20852 KB |
Output is correct |
4 |
Correct |
21 ms |
20852 KB |
Output is correct |
5 |
Correct |
27 ms |
20864 KB |
Output is correct |
6 |
Correct |
21 ms |
20880 KB |
Output is correct |
7 |
Correct |
21 ms |
20884 KB |
Output is correct |
8 |
Correct |
20 ms |
20944 KB |
Output is correct |
9 |
Correct |
23 ms |
20996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
20728 KB |
Output is correct |
2 |
Correct |
23 ms |
20852 KB |
Output is correct |
3 |
Correct |
21 ms |
20852 KB |
Output is correct |
4 |
Correct |
21 ms |
20852 KB |
Output is correct |
5 |
Correct |
27 ms |
20864 KB |
Output is correct |
6 |
Correct |
21 ms |
20880 KB |
Output is correct |
7 |
Correct |
21 ms |
20884 KB |
Output is correct |
8 |
Correct |
20 ms |
20944 KB |
Output is correct |
9 |
Correct |
23 ms |
20996 KB |
Output is correct |
10 |
Correct |
30 ms |
22472 KB |
Output is correct |
11 |
Correct |
44 ms |
22532 KB |
Output is correct |
12 |
Correct |
42 ms |
24048 KB |
Output is correct |
13 |
Correct |
30 ms |
24048 KB |
Output is correct |
14 |
Correct |
32 ms |
24048 KB |
Output is correct |
15 |
Correct |
36 ms |
24048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4034 ms |
327972 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
20728 KB |
Output is correct |
2 |
Correct |
23 ms |
20852 KB |
Output is correct |
3 |
Correct |
21 ms |
20852 KB |
Output is correct |
4 |
Correct |
21 ms |
20852 KB |
Output is correct |
5 |
Correct |
27 ms |
20864 KB |
Output is correct |
6 |
Correct |
21 ms |
20880 KB |
Output is correct |
7 |
Correct |
21 ms |
20884 KB |
Output is correct |
8 |
Correct |
20 ms |
20944 KB |
Output is correct |
9 |
Correct |
23 ms |
20996 KB |
Output is correct |
10 |
Correct |
30 ms |
22472 KB |
Output is correct |
11 |
Correct |
44 ms |
22532 KB |
Output is correct |
12 |
Correct |
42 ms |
24048 KB |
Output is correct |
13 |
Correct |
30 ms |
24048 KB |
Output is correct |
14 |
Correct |
32 ms |
24048 KB |
Output is correct |
15 |
Correct |
36 ms |
24048 KB |
Output is correct |
16 |
Execution timed out |
4034 ms |
327972 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |