/*
PROG: joi183b
LANG: C++11
_____
.' '.
/ 0 0 \
| ^ |
| \ / |
\ '---' /
'._____.'
*/
#include <bits/stdc++.h>
using namespace std;
template<class T>
void readi(T &x)
{
T input = 0;
bool negative = false;
char c = ' ';
while (c < '-')
{
c = getchar();
}
if (c == '-')
{
negative = true;
c = getchar();
}
while (c >= '0')
{
input = input * 10 + (c - '0');
c = getchar();
}
if (negative)
{
input = -input;
}
x = input;
}
template<class T>
void printi(T output)
{
if (output == 0)
{
putchar('0');
return;
}
if (output < 0)
{
putchar('-');
output = -output;
}
int aout[20];
int ilen = 0;
while(output)
{
aout[ilen] = ((output % 10));
output /= 10;
ilen++;
}
for (int i = ilen - 1; i >= 0; i--)
{
putchar(aout[i] + '0');
}
return;
}
template<class T>
void ckmin(T &a, T b)
{
a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
a = max(a, b);
}
long long randomize(long long mod)
{
return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;
#define MAGIC 107
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 200013
template<class T>
T normalize(T x, T mod = INF)
{
return (((x % mod) + mod) % mod);
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, vector<int> > piv;
int N, M, Q;
vector<int> edge[MAXN];
bool seen[MAXN];
vector<piv> queries[MAXN];
vector<pii> best[MAXN];
int dist[MAXN];
int ans[MAXN];
int32_t main()
{
ios_base::sync_with_stdio(0);
srand(time(0));
// cout << fixed << setprecision(12);
// cerr << fixed << setprecision(12);
if (fopen("joi183b.in", "r"))
{
freopen ("joi183b.in", "r", stdin);
freopen ("joi183b.out", "w", stdout);
}
cin >> N >> M >> Q;
for (int i = 0; i < M; i++)
{
int u, v;
cin >> u >> v;
u--;
v--;
edge[v].PB(u);
}
for (int i = 0; i < Q; i++)
{
int u, sz;
cin >> u >> sz;
u--;
vector<int> vec;
for (int j = 0; j < sz; j++)
{
int v;
cin >> v;
v--;
vec.PB(v);
}
queries[u].PB(MP(i, vec));
ans[i] = -1;
}
for (int i = 0; i < N; i++)
{
dist[i] = -INF;
}
for (int u = 0; u < N; u++)
{
vector<int> active;
dist[u] = 0;
active.PB(u);
for (int v : edge[u])
{
for (pii x : best[v])
{
ckmax(dist[x.se], x.fi + 1);
active.PB(x.se);
}
}
sort(active.begin(), active.end());
active.erase(unique(active.begin(), active.end()), active.end());
for (int v : active)
{
best[u].PB(MP(dist[v], v));
}
sort(best[u].begin(), best[u].end());
reverse(best[u].begin(), best[u].end());
while(best[u].size() > MAGIC)
{
best[u].pop_back();
}
for (int v : edge[u])
{
for (pii x : best[v])
{
dist[x.se] = -INF;
}
}
}
// for (int i = 0; i < N; i++)
// {
// cerr << "vertex " << i << ":\n";
// for (pii x : best[i])
// {
// cerr << "dist " << x.fi << " vertex " << x.se << '\n';
// }
// }
for (int u = 0; u < N; u++)
{
for (piv q : queries[u])
{
int qid = q.fi;
vector<int> bans = q.se;
for (int v : bans)
{
seen[v] = true;
}
if (bans.size() < MAGIC)
{
for (auto y : best[u])
{
int v = y.se;
if (!seen[v])
{
ans[qid] = y.fi;
break;
}
}
}
else
{
for (int v = u; v >= 0; v--)
{
dist[v] = -INF;
}
dist[u] = 0;
for (int v = u; v >= 0; v--)
{
// cerr << v << ' ' << dist[v] << endl;
for (int w : edge[v])
{
ckmax(dist[w], dist[v] + 1);
}
if (!seen[v])
{
ckmax(ans[qid], dist[v]);
}
}
}
for (int v : bans)
{
seen[v] = false;
}
}
//if sum of # of u-queries is >= sqrtN you can probably brute
//otherwise sum of banned is <sqrtN, so you store the best sqrtN guys?
}
for (int i = 0; i < Q; i++)
{
cout << ans[i] << '\n';
}
//longest path starting from u that doesn't end at one of these specific nodes
//so you just have a graph with no cycles and you can toposort
// cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
return 0;
}
Compilation message
bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:133:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen ("joi183b.in", "r", stdin);
~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:134:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen ("joi183b.out", "w", stdout);
~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
14472 KB |
Output is correct |
2 |
Correct |
17 ms |
14472 KB |
Output is correct |
3 |
Correct |
16 ms |
14556 KB |
Output is correct |
4 |
Correct |
17 ms |
14604 KB |
Output is correct |
5 |
Correct |
23 ms |
15192 KB |
Output is correct |
6 |
Correct |
26 ms |
15192 KB |
Output is correct |
7 |
Correct |
22 ms |
15192 KB |
Output is correct |
8 |
Correct |
31 ms |
15832 KB |
Output is correct |
9 |
Correct |
22 ms |
15832 KB |
Output is correct |
10 |
Correct |
20 ms |
15832 KB |
Output is correct |
11 |
Correct |
28 ms |
15832 KB |
Output is correct |
12 |
Correct |
26 ms |
15832 KB |
Output is correct |
13 |
Correct |
29 ms |
15832 KB |
Output is correct |
14 |
Correct |
24 ms |
15832 KB |
Output is correct |
15 |
Correct |
26 ms |
15832 KB |
Output is correct |
16 |
Correct |
25 ms |
15832 KB |
Output is correct |
17 |
Correct |
27 ms |
15832 KB |
Output is correct |
18 |
Correct |
17 ms |
15832 KB |
Output is correct |
19 |
Correct |
28 ms |
15832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
14472 KB |
Output is correct |
2 |
Correct |
17 ms |
14472 KB |
Output is correct |
3 |
Correct |
16 ms |
14556 KB |
Output is correct |
4 |
Correct |
17 ms |
14604 KB |
Output is correct |
5 |
Correct |
23 ms |
15192 KB |
Output is correct |
6 |
Correct |
26 ms |
15192 KB |
Output is correct |
7 |
Correct |
22 ms |
15192 KB |
Output is correct |
8 |
Correct |
31 ms |
15832 KB |
Output is correct |
9 |
Correct |
22 ms |
15832 KB |
Output is correct |
10 |
Correct |
20 ms |
15832 KB |
Output is correct |
11 |
Correct |
28 ms |
15832 KB |
Output is correct |
12 |
Correct |
26 ms |
15832 KB |
Output is correct |
13 |
Correct |
29 ms |
15832 KB |
Output is correct |
14 |
Correct |
24 ms |
15832 KB |
Output is correct |
15 |
Correct |
26 ms |
15832 KB |
Output is correct |
16 |
Correct |
25 ms |
15832 KB |
Output is correct |
17 |
Correct |
27 ms |
15832 KB |
Output is correct |
18 |
Correct |
17 ms |
15832 KB |
Output is correct |
19 |
Correct |
28 ms |
15832 KB |
Output is correct |
20 |
Correct |
880 ms |
17268 KB |
Output is correct |
21 |
Correct |
894 ms |
17368 KB |
Output is correct |
22 |
Correct |
941 ms |
17368 KB |
Output is correct |
23 |
Correct |
1012 ms |
17720 KB |
Output is correct |
24 |
Execution timed out |
2069 ms |
129256 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
14472 KB |
Output is correct |
2 |
Correct |
17 ms |
14472 KB |
Output is correct |
3 |
Correct |
16 ms |
14556 KB |
Output is correct |
4 |
Correct |
17 ms |
14604 KB |
Output is correct |
5 |
Correct |
23 ms |
15192 KB |
Output is correct |
6 |
Correct |
26 ms |
15192 KB |
Output is correct |
7 |
Correct |
22 ms |
15192 KB |
Output is correct |
8 |
Correct |
31 ms |
15832 KB |
Output is correct |
9 |
Correct |
22 ms |
15832 KB |
Output is correct |
10 |
Correct |
20 ms |
15832 KB |
Output is correct |
11 |
Correct |
28 ms |
15832 KB |
Output is correct |
12 |
Correct |
26 ms |
15832 KB |
Output is correct |
13 |
Correct |
29 ms |
15832 KB |
Output is correct |
14 |
Correct |
24 ms |
15832 KB |
Output is correct |
15 |
Correct |
26 ms |
15832 KB |
Output is correct |
16 |
Correct |
25 ms |
15832 KB |
Output is correct |
17 |
Correct |
27 ms |
15832 KB |
Output is correct |
18 |
Correct |
17 ms |
15832 KB |
Output is correct |
19 |
Correct |
28 ms |
15832 KB |
Output is correct |
20 |
Correct |
880 ms |
17268 KB |
Output is correct |
21 |
Correct |
894 ms |
17368 KB |
Output is correct |
22 |
Correct |
941 ms |
17368 KB |
Output is correct |
23 |
Correct |
1012 ms |
17720 KB |
Output is correct |
24 |
Execution timed out |
2069 ms |
129256 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |