oj.uz

Submission #298372

# Submission time Handle Problem Language Result Execution time Memory
298372 2020-09-12T18:44:50 Z Rayaabualjamal Split the Attractions (IOI19_split) C++14
18 / 100
 293 ms 14024 KB 
#include "split.h"
#include <cassert>
 
#include <iostream> 
#include <set> 
#include <iterator>
#include <cmath>
#include <algorithm>
#include <vector> 
#include <map> 
#include <cstdio>
#define rep(i,a,b) for(int i = a; i<b; i++)
#define per(i,a,b) for(int i = a; i>=b; i--)
#define pb push_back
#define se second
#define mp make_pair
#define fi first
using namespace std;
vector <int> ans;
vector < vector <int> > ve;
vector < pair <int, int> > ce;
int dfs(int v){
	if(ans[v] == 4|| ans[v]==ce[1].se)return 0;
	int cnt = 1;
	ans[v]=4;
	for(int l:ve[v]){
		if(ans[l]!=4&&ans[l]!=ce[1].se){
			cnt+=dfs(l);
		}
	}
	return cnt;
}
void bfs2(int v){
	int h = ce[0].first;
	int d = ce[0].se;
	set<int> s;
	s.insert(v);
	ans[v] = d;
	h--;
	while(!s.empty()&&h){
		int best = *s.begin();
		s.erase(s.begin());
		for(int k:ve[best]){
			if(h&&ans[k]==4){
				ans[k]=d;
				h--;
				s.insert(k);
			}
		}
	}
}
void fix(){
	rep(i,0,ans.size()){
		if(ans[i]==4){
			ans[i]=ce[2].se;
		}
	}
}
bool bfs(int v){
	int h = ce[1].first;
	int d = ce[1].se;
	set< pair <int, int> > s;
	s.insert(mp(ve[v].size(),v));
	//cout << v << ":" << endl;
	while(!s.empty()&&h){
		int best = (*s.begin()).se;
		//cout << best << endl;
		s.erase(s.begin());
		if(ans[best]==d)continue;
		ans[best]=d;
		h--;
		if(h==0)break;
		for(int k:ve[best]){
			if(ans[k]!=d){
				s.insert(mp(ve[k].size(),k));
			}
		}
	}
	//cout << endl;
	rep(i,0,ans.size()){
		if(ans[i]!=d){
			int count  = dfs(i);
			//cout << v << " " << count << " " << i << endl;
			if(count >=ce[0].first){
				bfs2(i);
				fix();
				//cout << "here" << endl;
				return true;
			}
		}
	}
	return false;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	ce.pb(make_pair(a, 1));
	ce.pb(make_pair(b, 2));
	ce.pb(make_pair(c, 3));
	sort(ce.begin(), ce.end());
	ve.resize(n+1);
	rep(i,0,p.size()){
		ve[p[i]].pb(q[i]);
		ve[q[i]].pb(p[i]);
	}
	bool f = 0;
	rep(i,0,n){
		//cout << i << endl;
		ans.assign(n,ce[2].se);
		if(bfs(i)){
			f = 1;
			break;
		}
	}
	if(f)return ans;
	ans.assign(n,0);
	return ans;
}

Compilation message

split.cpp: In function 'void fix()':
split.cpp:12:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define rep(i,a,b) for(int i = a; i<b; i++)
......
   53 |  rep(i,0,ans.size()){
      |      ~~~~~~~~~~~~~~                 
split.cpp:53:2: note: in expansion of macro 'rep'
   53 |  rep(i,0,ans.size()){
      |  ^~~
split.cpp: In function 'bool bfs(int)':
split.cpp:12:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define rep(i,a,b) for(int i = a; i<b; i++)
......
   80 |  rep(i,0,ans.size()){
      |      ~~~~~~~~~~~~~~                 
split.cpp:80:2: note: in expansion of macro 'rep'
   80 |  rep(i,0,ans.size()){
      |  ^~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:12:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define rep(i,a,b) for(int i = a; i<b; i++)
......
  100 |  rep(i,0,p.size()){
      |      ~~~~~~~~~~~~                   
split.cpp:100:2: note: in expansion of macro 'rep'
  100 |  rep(i,0,p.size()){
      |  ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 0 ms 256 KB ok, correct split
4 Correct 1 ms 384 KB ok, correct split
5 Correct 0 ms 384 KB ok, correct split
6 Correct 0 ms 256 KB ok, correct split
7 Correct 89 ms 10360 KB ok, correct split
8 Correct 71 ms 9976 KB ok, correct split
9 Correct 83 ms 10104 KB ok, correct split
10 Correct 87 ms 12152 KB ok, correct split
11 Correct 88 ms 11128 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 116 ms 12408 KB ok, correct split
5 Correct 82 ms 9464 KB ok, correct split
6 Correct 92 ms 12124 KB ok, correct split
7 Correct 89 ms 10360 KB ok, correct split
8 Correct 139 ms 12536 KB ok, correct split
9 Correct 79 ms 9336 KB ok, correct split
10 Correct 108 ms 13552 KB ok, correct split
11 Correct 109 ms 13552 KB ok, correct split
12 Correct 114 ms 14024 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 109 ms 9460 KB ok, correct split
3 Correct 27 ms 3968 KB ok, correct split
4 Incorrect 1 ms 256 KB jury found a solution, contestant did not
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 1 ms 256 KB ok, no valid answer
3 Correct 0 ms 256 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 1 ms 256 KB ok, correct split
6 Correct 1 ms 256 KB ok, correct split
7 Correct 0 ms 256 KB ok, correct split
8 Correct 1 ms 256 KB ok, correct split
9 Correct 3 ms 640 KB ok, correct split
10 Correct 3 ms 640 KB ok, correct split
11 Correct 1 ms 384 KB ok, correct split
12 Correct 3 ms 640 KB ok, correct split
13 Correct 1 ms 256 KB ok, correct split
14 Correct 1 ms 256 KB ok, correct split
15 Correct 1 ms 256 KB ok, correct split
16 Correct 1 ms 256 KB ok, correct split
17 Correct 0 ms 256 KB ok, correct split
18 Correct 1 ms 256 KB ok, correct split
19 Correct 1 ms 384 KB ok, correct split
20 Correct 1 ms 384 KB ok, correct split
21 Incorrect 293 ms 632 KB jury found a solution, contestant did not
22 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 0 ms 256 KB ok, correct split
4 Correct 1 ms 384 KB ok, correct split
5 Correct 0 ms 384 KB ok, correct split
6 Correct 0 ms 256 KB ok, correct split
7 Correct 89 ms 10360 KB ok, correct split
8 Correct 71 ms 9976 KB ok, correct split
9 Correct 83 ms 10104 KB ok, correct split
10 Correct 87 ms 12152 KB ok, correct split
11 Correct 88 ms 11128 KB ok, correct split
12 Correct 0 ms 256 KB ok, correct split
13 Correct 0 ms 256 KB ok, correct split
14 Correct 1 ms 256 KB ok, correct split
15 Correct 116 ms 12408 KB ok, correct split
16 Correct 82 ms 9464 KB ok, correct split
17 Correct 92 ms 12124 KB ok, correct split
18 Correct 89 ms 10360 KB ok, correct split
19 Correct 139 ms 12536 KB ok, correct split
20 Correct 79 ms 9336 KB ok, correct split
21 Correct 108 ms 13552 KB ok, correct split
22 Correct 109 ms 13552 KB ok, correct split
23 Correct 114 ms 14024 KB ok, correct split
24 Correct 0 ms 256 KB ok, correct split
25 Correct 109 ms 9460 KB ok, correct split
26 Correct 27 ms 3968 KB ok, correct split
27 Incorrect 1 ms 256 KB jury found a solution, contestant did not
28 Halted 0 ms 0 KB -