| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1003536 | 2024-06-20T12:34:32 Z | andrei_iorgulescu | 늑대인간 (IOI18_werewolf) | C++14 | 1371 ms | 212540 KB |
#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
| # | 결과 | 실행 시간 | 메모리 | 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 | - |
| # | 결과 | 실행 시간 | 메모리 | 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 | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1371 ms | 212540 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | 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 | - |