#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int n,m,q;
vector<pair<int,int>> id_changes[200005];///pentru R incepand cu .first, am id-ul .second
vector<pair<int,pair<int,int>>> valori[200005];
vector<int> fii[200005];
int t[200005];
vector<int> queries[200005];
unordered_map<int,int> huh[200005];
int get_id(int cine,int mom)
{
for (auto it : valori[cine])
if (it.second.first <= mom and it.second.second >= mom)
return it.first;
return -1;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
n = N;
m = X.size();
q = S.size();
for (int i = 0; i < m; i++)
X[i]++,Y[i]++;
for (int i = 0; i < q; i++)
S[i]++,E[i]++,L[i]++,R[i]++;
for (int i = 1; i <= n; i++)
id_changes[i].push_back({i,i});
for (int i = 1; i <= n; i++)
t[i] = i,fii[i].push_back(i);
vector<pair<int,pair<int,int>>> e_wolf;
for (int i = 0; i < m; i++)
e_wolf.push_back({max(X[i],Y[i]),{X[i],Y[i]}});
sort(e_wolf.begin(),e_wolf.end());
for (auto it : e_wolf)
{
int x = it.second.first,y = it.second.second;
int mom = it.first;
if (t[x] == t[y])
continue;
x = t[x],y = t[y];
if (fii[x].size() < fii[y].size())
swap(x,y);
for (auto it : fii[y])
{
t[it] = x;
fii[x].push_back(it);
id_changes[it].push_back({mom,x});
}
fii[y].clear();
}
for (int i = 1; i <= n; i++)
fii[i].clear();
for (int i = 1; i <= n; i++)
{
t[i] = i;
fii[i].push_back(i);
for (int j = 0; j < id_changes[i].size(); j++)
{
if(j + 1 != id_changes[i].size() and id_changes[i][j] != id_changes[i][j + 1])
valori[i].push_back({id_changes[i][j].second,{id_changes[i][j].first,id_changes[i][j + 1].first - 1}});
else if (j + 1 == id_changes[i].size())
valori[i].push_back({id_changes[i][j].second,{id_changes[i][j].first,n}});
}
for (auto it : valori[i])
{
if (huh[i][it.first] == 0 or huh[i][it.first] >= it.second.first)
huh[i][it.first] = it.second.first;
}
}
vector<pair<int,pair<int,int>>> e_om;
for (int i = 0; i < m; i++)
e_om.push_back({min(X[i],Y[i]),{X[i],Y[i]}});
sort(e_om.begin(),e_om.end());
reverse(e_om.begin(),e_om.end());
for (int i = 0; i < q; i++)
queries[L[i]].push_back(i);
vector<int> answer(q);
int i1 = 0;
for (int l = n; l >= 1; l--)
{
while (i1 < m and e_om[i1].first >= l)
{
int x = e_om[i1].second.first,y = e_om[i1].second.second;
i1++;
///unesc cu muchia x--y
if (t[x] == t[y])
continue;
x = t[x],y = t[y];
if (fii[x].size() < fii[y].size())
swap(x,y);
for (auto it : fii[y])
{
t[it] = x;
fii[x].push_back(it);
}
for (auto it : huh[y])
{
if (huh[x][it.first] == 0 or huh[x][it.first] > it.second)
huh[x][it.first] = it.second;
}
huh[y].clear();
fii[y].clear();
}
for (auto it : queries[l])
{
int x = t[S[it]];
int cine = get_id(E[it],R[it]);
///daca am, in setul de valori ale lui x, pe id-ul cine cu interval care contine R[it], e bine
if (huh[x][cine] <= R[it] and huh[x][cine] != 0)
answer[it] = 1;
}
}
return answer;
}
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:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int j = 0; j < id_changes[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | if(j + 1 != id_changes[i].size() and id_changes[i][j] != id_changes[i][j + 1])
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:66:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | else if (j + 1 == id_changes[i].size())
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
30040 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
30044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
30040 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
30044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1371 ms |
212540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
30040 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
30044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
