Submission #46866

#	Time	Username	Problem	Language	Result	Execution time	Memory
46866		kyleliu	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2024 ms	217544 KiB

bitaro

#include <bits/stdc++.h> // PLEASE

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pp;
#define MAXN 100005
#define MAXM 1005
#define MAXP 25
#define A first
#define B second
#define MP make_pair
#define PB push_back
const ll INF = 2e9+13;
const ll MOD = 1e9+7;
const int K = 200;

int N, M, Q;
vector <pp> farth[MAXN];
vector <int> g[MAXN];
vector <int> f[MAXN];
int in[MAXN];
int dp[MAXN];
bool can[MAXN];
bool vis[MAXN];
void solve() {
	queue <int> q;
	memset(vis, 0, sizeof(vis));
	for(int i=1; i<=N; i++) {
		dp[i] = -1;
		if(in[i] == 0) {
			q.push(i);
			if(can[i]) dp[i] = 0;
		}
	}
	while(!q.empty()) {
		int u = q.front(); q.pop();
		if(can[u]) dp[u] = max(dp[u], 0);
		if(vis[u]) continue; vis[u] = 1;
		for(auto v : g[u]) {
			if(dp[u] >= 0) dp[v] = max(dp[v], dp[u] + 1);
			in[v]--;
			if(in[v] == 0) q.push(v);
		}
	}  
	for(int i=1; i<=N; i++) for(auto v : g[i]) in[v]++;
} 

bool cmp(pp a, pp b)
{
	return a.A > b.A;
}

vector <pp> add(vector <pp> a, vector <pp> b)
{
	vector <pp> ret;
	int p1 = 0; int p2 = 0;
	while((p1 < a.size() || p2 < b.size()) && ret.size() < K) {
		int v1 = -MAXN; int v2 = -MAXN;
		if(p1<a.size()) v1 = a[p1].A;
		if(p2<b.size()) v2 = b[p2].A + 1;
		if(v1 > v2) ret.PB({v1, a[p1++].B});
		else ret.PB({v2, b[p2++].B});
	}
	return ret;
}

void pre()
{
	for(int i=1; i<=N; i++) {
		farth[i].PB({0, i});
		for(auto v : f[i]) farth[i] = add(farth[i], farth[v]);
	}
}
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M >> Q;
	for(int i=1; i<=N; i++) can[i] = 1;
	for(int i=0; i<M; i++) {
		int a, b; cin >> a >> b;
		g[a].PB(b); in[b]++;
		f[b].PB(a);
	}
	pre();
	while(Q--) {
		int t, n;
		cin >> t >> n;
		if(n > K) {
			vector <int> v;
			for(int i=1; i<=n; i++) { int x; cin >> x; v.PB(x); }
			for(auto x : v) can[x] = 0;
			solve();
			cout << dp[t] << endl;
			for(auto x : v) can[x] = 1;
		}
		else {
			vector <int> v;
			for(int i=1; i<=n; i++) { int x; cin >> x; v.PB(x); }
			for(auto x : v) can[x] = 0;
			bool printed = 0;
			//cout << "TARG " << t << endl;
			for(auto x : farth[t]) {
			//	cout << "DIST " << x.A << " NODE " << x.B << endl;
				if(can[x.B]) {
					cout << x.A << endl;
					printed = 1; break;
				}
			}
			if(!printed) cout << -1 << endl;
			for(auto x : v) can[x] = 1;
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:39:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(vis[u]) continue; vis[u] = 1;
   ^~
bitaro.cpp:39:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(vis[u]) continue; vis[u] = 1;
                        ^~~
bitaro.cpp: In function 'std::vector<std::pair<int, int> > add(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:58:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((p1 < a.size() || p2 < b.size()) && ret.size() < K) {
         ~~~^~~~~~~~~~
bitaro.cpp:58:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((p1 < a.size() || p2 < b.size()) && ret.size() < K) {
                          ~~~^~~~~~~~~~
bitaro.cpp:60:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p1<a.size()) v1 = a[p1].A;
      ~~^~~~~~~~~
bitaro.cpp:61:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p2<b.size()) v2 = b[p2].A + 1;
      ~~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86