| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 298359 | Rayaabualjamal | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "split.h"
#include <cassert>
#include <iostream>
#include <set>
#include <queue>
#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
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;
queue <int> s;
s.push(v);
ans[v] = d;
h--;
while(!s.empty()&&h){
int best = s.front();
s.pop();
for(int k:ve[best]){
if(h&&ans[k]!=d){
ans[k]=d;
h--;
s.push(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;
}