oj.uz

Submission #62574

# Submission time Handle Problem Language Result Execution time Memory
62574 2018-07-29T06:40:03 Z qkxwsm Bitaro’s Party (JOI18_bitaro) C++11
7 / 100
 2000 ms 129256 KB 
/*
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);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 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

Subtask #2
0 / 7.0

# 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 -

Subtask #3
0 / 86.0

# 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 -