oj.uz

답안 #893464

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893464 2023-12-27T05:18:37 Z Jawad_Akbar_JJ Split the Attractions (IOI19_split) C++17
0 / 100
 59 ms 12552 KB 
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include "split.h"
#include <algorithm>
 
using namespace std;
const int N = 1e5 + 10;
 
vector<vector<int>> v;
vector<int> nei[N];
int A,B;
int mn[N];
int sz[N];
int hei[N];
bool seen[N];
int color[N];
bool found = false;
int K;
 
void dfs_color(int u,int c){
	if (seen[u])
		return;
	if (K<=0)
		return;
	color[u] = c;
	seen[u] = true;
	K--;
	for (int i : nei[u]){
		if (seen[i])
			continue;
		dfs_color(i,c);
	}
}
 
void dfs(int u,int h = 1){
	sz[u] = 1;
	hei[u] = h++;
	seen[u] = true;
	mn[u] = hei[u];
	for (int i : nei[u]){
		if (seen[i]){
			mn[u] = min(mn[u],hei[i]);
			continue;
		}
		dfs(i,h);
		sz[u] += sz[i];
		mn[u] = min(mn[u],mn[i]);
	}
}
 
// #################################### reset seen
bool called = false;
void call(int u,set<int> s,int c,int Sz){
	if (called)
		return;
	called = true;
	memset(seen,false,sizeof seen);
	seen[u] = true;
	color[u] = c;
	Sz--;
	K = Sz;
	for (int i : s)
		dfs_color(i,c);
	if (K>0){
		cout<<1/0<<endl;
	}
}
 
void dfs2(int u){
	seen[u] = true; 
	int p1 = sz[u];
	int p2 = sz[1] - sz[u];
 
	set<int> s;
 
	for (int  i : nei[u])
		if (!seen[i]){
          	if (found)
              	return;
			s.insert(i);
			dfs2(i);
		}
 
	if (p1>=A and p2>=B){
		call(u,s,v[0][1],A);
		K = B;
		dfs_color(1,v[1][1]);
		found = true;
		return;
	}
	else if (p1>=B and p2>=A){
		call(u,s,v[1][1],B);
		K = A;
		dfs_color(1,v[0][1]);
		found = true;
		return;
	}
 
	for (int i : nei[u]){
		if (seen[i])
			continue;
 
		if (found)
			return;
		
		if (p1 - sz[i] >= A and mn[i] < hei[u]){
			s.erase(i);
			p1 -= sz[i];
			p2 += sz[i];
		}
		if (p1>=A and p2>=B){
			call(u,s,v[0][1],A);
			K = B;
			dfs_color(1,v[1][1]);
			found = true;
			return;
		}
		else if (p1>=B and p2>=A){
			call(u,s,v[1][1],B);
			K = A;
			dfs_color(1,v[0][1]);
			found = true;
			return;
		}
	}
}
 
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
	int m = p.size();
 
	for (int i=0;i<m;i++){
		p[i]++;
		q[i]++;
		nei[p[i]].push_back(q[i]);
		nei[q[i]].push_back(p[i]);
	}
	v.push_back({a,1});
	v.push_back({b,2});
	v.push_back({c,3});
 
	sort(begin(v),end(v));
 
	A = v[0][0];
	B = v[1][0];
 
	dfs(1,1);
 
	memset(seen,false,sizeof seen);
 
	dfs2(1);
 	if (K>0){
 		cout<<1/0<<endl;
 	}
	vector<int> col;
	if (!found){
		for (int i=1;i<=n;i++)
			col.push_back(0);
		return col;
	}
	for (int i=1;i<=n;i++){
		if (color[i]==0)
			col.push_back(v[2][1]);
		else
			col.push_back(color[i]);
	}
	return col;
}

Compilation message

split.cpp: In function 'void call(int, std::set<int>, int, int)':
split.cpp:67:10: warning: division by zero [-Wdiv-by-zero]
   67 |   cout<<1/0<<endl;
      |         ~^~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:154:11: warning: division by zero [-Wdiv-by-zero]
  154 |    cout<<1/0<<endl;
      |          ~^~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Runtime error 4 ms 8284 KB Execution killed with signal 4
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 8284 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Correct 59 ms 9804 KB ok, correct split
3 Runtime error 17 ms 12552 KB Execution killed with signal 4
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 8284 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Runtime error 4 ms 8284 KB Execution killed with signal 4
3 Halted 0 ms 0 KB -