oj.uz

Submission #95465

# Submission time Handle Problem Language Result Execution time Memory
95465 2019-02-01T12:46:34 Z Retro3014 Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 23 ms 5656 KB 
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <math.h>

using namespace std;
#define MAX_N 100000


int N, M, Q;
int Y, SQ;
vector<int> gp[MAX_N+1];
struct S{
	S (int idx, int data) : idx(idx), data(data) {}
	int idx, data;
	bool operator <(const S &a)const{
		return data>a.data;
	}
};
vector<S> vt[MAX_N+1];
struct QUERY{
	int t, y;
	vector<int> c;
};
vector<QUERY> Query;


bool chk[MAX_N+1];
int dist[MAX_N+1];

void solve_query(QUERY now){
	for(int i=0; i<now.y; i++){
		chk[now.c[i]] = true;
	}
	//if(now.y>=SQ){
		int ans = -1;
		for(int i = now.t; i>=1; i--){
			if(i!=now.t && dist[i]==0){
				continue;
			}
			if(!chk[i]){
				ans = max(ans, dist[i]);
			}
			for(int j=0; j<gp[i].size(); j++){
				dist[gp[i][j]] = max(dist[gp[i][j]], dist[i]+1);
			}
			dist[i] = 0;
		}
		printf("%d\n", ans);
	/*}else{
		int idx = 0;
		while(idx<vt[now.t].size()){
			if(chk[vt[now.t][idx].idx])	idx++;
			else break;
		}
		if(idx==vt[now.t].size())	printf("-1\n");
		else	printf("%d\n", vt[now.t][idx].data);
	}*/
	for(int i=0; i<now.y; i++){
		chk[now.c[i]] = false;
	}
}


void solve(){
	SQ = sqrt(Y);
	for(int i=1; i<=N; i++){
		vt[i].push_back({i, 0});
		for(int j=0; j<gp[i].size(); j++){
			for(int k=0; k<vt[gp[i][j]].size(); k++){
				vt[i].push_back({vt[gp[i][j]][k].idx, vt[gp[i][j]][k].data+1});
			}
		}
		sort(vt[i].begin(), vt[i].end());
		int index = 0, cnt = 0;
		while(index<vt[i].size() && cnt<SQ){
			if(!chk[vt[i][index].idx]){
				cnt++;
				chk[vt[i][index].idx] = true;
			}else{
				vt[i][index].data = -1;
			}
			index++;
		}
		sort(vt[i].begin(), vt[i].end());
		while(vt[i].size()>SQ || vt[i].back().data==-1)	vt[i].pop_back();
		for(int j=0; j<vt[i].size(); j++){
			chk[vt[i][j].idx] = false;
		}
	}
}

int main(){
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=0; i<M; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		gp[b].push_back(a);
	}
	for(int i=0; i<Q; i++){
		QUERY tmp;
		scanf("%d%d", &tmp.t, &tmp.y);
		Y+=tmp.y;
		while(!tmp.c.empty())	tmp.c.pop_back();
		for(int i=0; i<tmp.y; i++){
			int x;
			scanf("%d", &x); tmp.c.push_back(x);
		}
		Query.push_back(tmp);
	}
	//cout<<1<<endl;
	solve();
	for(int i=0; i<Query.size(); i++){
		solve_query(Query[i]);
	}
	return 0;
}

Compilation message

bitaro.cpp: In function 'void solve_query(QUERY)':
bitaro.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<gp[i].size(); j++){
                 ~^~~~~~~~~~~~~
bitaro.cpp: In function 'void solve()':
bitaro.cpp:70:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<gp[i].size(); j++){
                ~^~~~~~~~~~~~~
bitaro.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<vt[gp[i][j]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:77:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(index<vt[i].size() && cnt<SQ){
         ~~~~~^~~~~~~~~~~~~
bitaro.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(vt[i].size()>SQ || vt[i].back().data==-1) vt[i].pop_back();
         ~~~~~~~~~~~~^~~
bitaro.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<vt[i].size(); j++){
                ~^~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<Query.size(); i++){
               ~^~~~~~~~~~~~~
bitaro.cpp:95: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:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &tmp.t, &tmp.y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x); tmp.c.push_back(x);
    ~~~~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 8 ms 5368 KB Output is correct
7 Correct 8 ms 5368 KB Output is correct
8 Correct 8 ms 5624 KB Output is correct
9 Correct 8 ms 5624 KB Output is correct
10 Correct 8 ms 5628 KB Output is correct
11 Correct 9 ms 5624 KB Output is correct
12 Correct 8 ms 5496 KB Output is correct
13 Correct 8 ms 5656 KB Output is correct
14 Correct 8 ms 5368 KB Output is correct
15 Correct 7 ms 5368 KB Output is correct
16 Correct 23 ms 5496 KB Output is correct
17 Correct 8 ms 5496 KB Output is correct
18 Correct 8 ms 5368 KB Output is correct
19 Incorrect 7 ms 5496 KB Output isn't correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 8 ms 5368 KB Output is correct
7 Correct 8 ms 5368 KB Output is correct
8 Correct 8 ms 5624 KB Output is correct
9 Correct 8 ms 5624 KB Output is correct
10 Correct 8 ms 5628 KB Output is correct
11 Correct 9 ms 5624 KB Output is correct
12 Correct 8 ms 5496 KB Output is correct
13 Correct 8 ms 5656 KB Output is correct
14 Correct 8 ms 5368 KB Output is correct
15 Correct 7 ms 5368 KB Output is correct
16 Correct 23 ms 5496 KB Output is correct
17 Correct 8 ms 5496 KB Output is correct
18 Correct 8 ms 5368 KB Output is correct
19 Incorrect 7 ms 5496 KB Output isn't correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 8 ms 5368 KB Output is correct
7 Correct 8 ms 5368 KB Output is correct
8 Correct 8 ms 5624 KB Output is correct
9 Correct 8 ms 5624 KB Output is correct
10 Correct 8 ms 5628 KB Output is correct
11 Correct 9 ms 5624 KB Output is correct
12 Correct 8 ms 5496 KB Output is correct
13 Correct 8 ms 5656 KB Output is correct
14 Correct 8 ms 5368 KB Output is correct
15 Correct 7 ms 5368 KB Output is correct
16 Correct 23 ms 5496 KB Output is correct
17 Correct 8 ms 5496 KB Output is correct
18 Correct 8 ms 5368 KB Output is correct
19 Incorrect 7 ms 5496 KB Output isn't correct