oj.uz

Submission #986949

# Submission time Handle Problem Language Result Execution time Memory
986949 2024-05-21T15:47:58 Z PagodePaiva Split the Attractions (IOI19_split) C++17
11 / 100
 66 ms 16592 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

vector <int> g[N];
int pai[N];
int folha;
int mark[N];

void dfs(int v, int p){
	int con = 0;
	pai[v] = p;
	mark[v] = 1;
	for(auto x : g[v]){
		if(x == p) continue;
		if(mark[x] == 1) continue;
		con++;
		dfs(x, v);
	}
	if(con == 0) folha = v;
}

int res[N];

void solve(int v, int &tam){
	if(tam == 0) return;
	tam--;
	res[v] = 2;
	mark[v] = 1;
	for(auto x : g[v]){
		if(mark[x]) continue;
		solve(x, tam);
	}
	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++){
		int a = p[i], b = q[i];
		a++;
		b++;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 1);
	memset(mark, 0, sizeof mark);
	res[folha] = 1;
	mark[folha] = 1;
	solve(pai[folha], b);
	vector <int> ans;
	for(int i = 1;i <= n;i++){
		if(res[i] == 0) res[i] = 3;
		ans.push_back(res[i]);
	}
	return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB ok, correct split
2 Correct 1 ms 3780 KB ok, correct split
3 Correct 1 ms 3676 KB ok, correct split
4 Incorrect 2 ms 3676 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB ok, correct split
2 Correct 1 ms 3676 KB ok, correct split
3 Correct 1 ms 3676 KB ok, correct split
4 Correct 53 ms 14848 KB ok, correct split
5 Correct 38 ms 10456 KB ok, correct split
6 Correct 45 ms 16592 KB ok, correct split
7 Correct 42 ms 14296 KB ok, correct split
8 Correct 66 ms 13780 KB ok, correct split
9 Correct 40 ms 9660 KB ok, correct split
10 Correct 35 ms 10444 KB ok, correct split
11 Correct 33 ms 10452 KB ok, correct split
12 Correct 34 ms 10964 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3676 KB invalid split: #1=1, #2=1, #3=3
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3676 KB invalid split: #1=1, #2=2, #3=6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB ok, correct split
2 Correct 1 ms 3780 KB ok, correct split
3 Correct 1 ms 3676 KB ok, correct split
4 Incorrect 2 ms 3676 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -