이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Problem: C - Bitaro's Party
// Contest: Virtual Judge - Square root tech
// URL: https://vjudge.net/contest/671583#problem/C
// Memory Limit: 507 MB
// Time Limit: 2000 ms
//
// By Muaath Alqarni
// Blog: https://muaath5.githib.io/blog
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 1e5+5, SQ = 300;
int n, m, q;
vector<int> adj[N];
int len[N];
pair<int, int> dp[N][SQ];
char mp[N];
int dp2[N];
static inline int read()
{
int x = 0;char ch = getchar();
while (ch < '0' || ch>'9') ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x;
}
static inline void print(const int &x) {
if (x > 9)print(x / 10);
putchar('0' + x % 10);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
n=read(),m=read(),q=read();
for (int i = 0; i < m; i++) {
int u=read(), v=read();
adj[v].push_back(u);
}
// precalc
vector<pii> res;
res.reserve(SQ);
for (int i = 1; i <= n; i++) {
len[i] = 1;
dp[i][0] = {0, i};
for (int j : adj[i]) {
vector<bool> used(n+1);
res.clear();
int p1 = 0, p2 = 0;
while (p1 < len[i] && p2 < len[j]) {
if (used[dp[i][p1].second]) {
p1++;
continue;
}
if (used[dp[j][p2].second]) {
p2++;
continue;
}
if (dp[i][p1].first > dp[j][p2].first+1)
used[dp[i][p1].second] = 1, res.push_back(dp[i][p1++]);
else {
used[dp[j][p2].second] = 1;
res.push_back({dp[j][p2].first+1, dp[j][p2].second});
p2++;
}
}
while (p1 < len[i] && res.size() < SQ) {
if (!used[dp[i][p1].second])
used[dp[i][p1].second] = 1, res.push_back(dp[i][p1]);
p1++;
}
while (p2 < len[j] && res.size() < SQ) {
if (!used[dp[j][p2].second])
used[dp[j][p2].second] = 1, res.push_back({dp[j][p2].first+1, dp[j][p2].second});
p2++;
}
sort(res.begin(), res.end(), greater<>());
len[i] = res.size();
for (int x = 0; x < len[i]; x++)
dp[i][x] = res[x];
}
}
while (q--) {
int t=read(), y=read();
vector<int> c(y);
for (int &i : c) {
i=read();
mp[i] = 1;
}
if (y >= SQ) {
for (int i = 1; i <= t; i++) {
for (int prv : adj[i]) {
if (!mp[prv] || dp2[prv] > 0)
dp2[i] = max(dp2[i], dp2[prv]+1);
}
}
if (dp2[t] == 0 && mp[t])
putchar('-'),putchar('1');
else
print(dp2[t]);
} else {
bool ok = false;
for (int i = 0; i < len[t]; i++) {
if (!mp[dp[t][i].second]) {
print(dp[t][i].first);
ok = true;
break;
}
}
if (!ok)
putchar('-'),putchar('1');
}
putchar('\n');
for (int &i : c) {
mp[i] = 0;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |