Submission #44397

#	Time	Username	Problem	Language	Result	Execution time	Memory
44397		Bruteforceman	Bitaro’s Party (JOI18_bitaro)	C++11	7 / 100	2013 ms	258552 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

struct pii {
	int first, second;
	pii (int first, int second) : first(first), second(second) {};
	pii () {}
};


const int magic = 400; //  sqrt(100000);
vector <pii> dp[100010];
vector <int> g[100010];
vector <int> grp[100010];

bool done[100010];
bool aux[100010];

vector <pii> merge(vector <pii> &a, vector <pii> &b) {
	vector <pii> ans;
	int l = 0;
	int r = 0;
	while(l < a.size() || r < b.size()) {
		if(ans.size() == magic) break;
		
		if(l == a.size()) {
			if(aux[b[r].first] == false) ans.push_back(b[r]);
			aux[b[r].first] = true;
			++r;
		}
		else if (r == b.size()) {
			if(aux[a[l].first] == false) ans.push_back(a[l]);
			aux[a[l].first] = true;
			++l;
		}
		else if (a[l].second < b[r].second) {
			if(aux[b[r].first] == false) ans.push_back(b[r]);
			aux[b[r].first] = true;
			++r;
		}
		else {
			if(aux[a[l].first] == false) ans.push_back(a[l]);
			aux[a[l].first] = true;
			++l;
		}
	}
	for(auto i : ans) {
		aux[i.first] = false;
	}
	return ans;
}

void dfs(int x) {
	if(done[x]) return ;
	done[x] = true;
	dp[x].push_back(pii(x, 0));
	for(auto i : g[x]) {
		dfs(i);
		vector <pii> v;
		for(auto j : dp[i]) {
			v.push_back(pii(j.first, j.second + 1));
		}
		dp[x] = merge(dp[x], v);
	}
}

bool bad[100010];
int arr[100010];
int root;
const int inf = 1000000000;

void conquer(int x) {
	if(arr[x] != -1) return ; 
	if(root == x) {
		arr[x] = 0;
		return ;
	}
	arr[x] = -inf;
	for(auto i : grp[x]) {
		conquer(i);
		arr[x] = max(arr[x], 1 + arr[i]);
	}
	return ;
}


int main() {
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);
	for(int i = 1; i <= m; i++) {
		int p, q;
		scanf("%d %d", &p, &q);
		g[q].push_back(p);
		grp[p].push_back(q);
	}
	for(int i = 1; i <= n; i++) {
		dfs(i);
	}
	for(int i = 1; i <= q; i++) {
		int t, y;
		scanf("%d %d", &t, &y);
		vector <int> v;
		for(int j = 0; j < y; j++) {
			int x;
			scanf("%d", &x);
			v.push_back(x);
			bad[x] = true;
		}
		int ans = -1;
		if(y < magic) {
			for(auto j : dp[t]) {
				if(!bad[j.first]) {
					ans = j.second;
					break;
				}
			}
		} else {
			memset(arr, -1, sizeof arr);
			root = t;
			for(int j = 1; j <= n; j++) {
				conquer(j);
				if(!bad[j]) ans = max(ans, arr[j]);
			}
		}
		printf("%d\n", ans);
		for(int j : v) {
			bad[j] = false;
		}
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<pii> merge(std::vector<pii>&, std::vector<pii>&)':
bitaro.cpp:23:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(l < a.size() || r < b.size()) {
        ~~^~~~~~~~~~
bitaro.cpp:23:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(l < a.size() || r < b.size()) {
                        ~~^~~~~~~~~~
bitaro.cpp:26:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(l == a.size()) {
      ~~^~~~~~~~~~~
bitaro.cpp:31:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if (r == b.size()) {
            ~~^~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~

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