oj.uz

Submission #965450

# Submission time Handle Problem Language Result Execution time Memory
965450 2024-04-18T15:19:38 Z goduadzesaba Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 2 ms 8792 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,B=400;
int n,m,q,x,y,z,cur,ans[N],bb[N]; bool b[N],bl;
vector <int> v[N],p[N];
vector <pair<int,int> > d[N],t;
signed main(){
	cin>>n>>m>>q;
	while (m--){
		cin>>x>>y;
		v[x].push_back(y);
		p[y].push_back(x);
	}
	for (int i=1; i<=n; i++){
		d[i].push_back({0,i});
		for (int j:p[i]){
			x=0; y=0; t.clear();
			while ((x<d[i].size() || y<d[j].size()) && t.size()<B){
				if (y==d[j].size() || d[i][x].first>=d[j][y].first+1){
					z=x;
					while (x<d[i].size() && d[i][x].first==d[i][z].first && t.size()<B){
						t.push_back(d[i][x]); x++;
					}
				}
				if (x==d[i].size() || d[i][x].first<=d[j][y].first+1){
					z=y;
					while (y<d[j].size() && d[j][y].first==d[j][z].first && t.size()<B){
						t.push_back({d[j][y].first+1,d[j][y].second}); y++;
					}
				}
			}
			d[i]=t;
		}
		cout<<i<<'\n';
		for (auto j:d[i]) cout<<j.first<<' '<<j.second<<"  "; cout<<'\n';
	}
	while (q--){
		cin>>cur>>m;
		for (int i=0; i<m; i++){
			cin>>bb[i]; b[bb[i]]=1; 
		}
		if (m<B){
			bl=0;
			for (auto i:d[cur]){
				if (b[i.second]) continue;
				cout<<i.first<<'\n'; bl=1; break;
			}
			if (bl==0) cout<<-1<<'\n';
		}
		else{
			for (int i=1; i<=n; i++){
				if (b[i]) ans[i]=-N;
				else ans[i]=0;
			}
			for (int i=1; i<=cur; i++){
				for (int j:v[i])
					ans[j]=max(ans[j],ans[i]+1);
			}
			if (ans[cur]<0) cout<<-1;
			else cout<<ans[cur]; cout<<'\n';
		}
		for (int i=0; i<m; i++){
			b[bb[i]]=1; 
		}
	}
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:19:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |    while ((x<d[i].size() || y<d[j].size()) && t.size()<B){
      |            ~^~~~~~~~~~~~
bitaro.cpp:19:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |    while ((x<d[i].size() || y<d[j].size()) && t.size()<B){
      |                             ~^~~~~~~~~~~~
bitaro.cpp:20:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     if (y==d[j].size() || d[i][x].first>=d[j][y].first+1){
      |         ~^~~~~~~~~~~~~
bitaro.cpp:22:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |      while (x<d[i].size() && d[i][x].first==d[i][z].first && t.size()<B){
      |             ~^~~~~~~~~~~~
bitaro.cpp:26:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if (x==d[i].size() || d[i][x].first<=d[j][y].first+1){
      |         ~^~~~~~~~~~~~~
bitaro.cpp:28:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |      while (y<d[j].size() && d[j][y].first==d[j][z].first && t.size()<B){
      |             ~^~~~~~~~~~~~
bitaro.cpp:36:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   36 |   for (auto j:d[i]) cout<<j.first<<' '<<j.second<<"  "; cout<<'\n';
      |   ^~~
bitaro.cpp:36:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   36 |   for (auto j:d[i]) cout<<j.first<<' '<<j.second<<"  "; cout<<'\n';
      |                                                         ^~~~
bitaro.cpp:61:4: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   61 |    else cout<<ans[cur]; cout<<'\n';
      |    ^~~~
bitaro.cpp:61:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   61 |    else cout<<ans[cur]; cout<<'\n';
      |                         ^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Halted 0 ms 0 KB -