oj.uz

Submission #440458

# Submission time Handle Problem Language Result Execution time Memory
440458 2021-07-02T10:04:13 Z antontsiorvas Fountain Parks (IOI21_parks) C++17
5 / 100
 101 ms 27640 KB 
#include "parks.h"

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

int fount2[200005], fount4[200005];
int sy2[200005], sy4[200005];
int numofvis;
vector<int> adj[200005];
map<int,int> emf;
bool visited[200005];

bool compare2(int a, int b){	return sy2[a] < sy2[b];	}

bool compare4(int a, int b){	return sy4[a] < sy4[b];	}

void dfs(int v){
	visited[v] = true;
	numofvis++;
	int len = adj[v].size();
	for(int i=0; i<len; i++){
		int to = adj[v][i];
		if(!visited[to]) dfs(to);
	}
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
		build({}, {}, {}, {});
        return 1;
    }
    int n = x.size(), cnt2=0, cnt4=0;
    for(int i=0; i<n; i++){
    	if(x[i] == 2){
    		fount2[cnt2] = i;
    		sy2[cnt2++] = y[i];
		}
		else{
			fount4[cnt4] = i;
    		sy4[cnt4++] = y[i];
		}
    	
	}
    std::sort(&fount2[0],&fount2[cnt2],compare2);
    std::sort(&sy2[0],&sy2[cnt2]);
    std::sort(&fount4[0],&fount4[cnt4],compare4);
    for(int i=1; i<cnt4; i++) emf[sy4[i]] = i; 
    emf[sy4[0]] = -1;
    std::sort(&sy4[0],&sy4[cnt4]);
    
    std::vector<int> u, v, a, b;
    
    if(cnt2 == 0){
    	for(int i=0; i<cnt4-1; i++){
	    	if(sy4[i+1]-sy4[i] != 2) return 0;
	    	u.push_back(fount4[i]);
	    	v.push_back(fount4[i+1]);
	    	a.push_back(5);
	    	b.push_back(sy4[i]+1);
		}
		build(u, v, a, b);
    	return 1;
	}
	if(cnt4 == 0){
    	for(int i=0; i<cnt2-1; i++){
	    	if(sy2[i+1]-sy2[i] != 2) return 0;
	    	u.push_back(fount2[i]);
	    	v.push_back(fount2[i+1]);
	    	a.push_back(1);
	    	b.push_back(sy2[i]+1);
		}
		build(u, v, a, b);
    	return 1;
	}
	
	for(int i=0; i<cnt2; i++){
		if(i == cnt2-1) continue;
		while(sy2[i+1]-sy2[i] == 2){
			u.push_back(fount2[i]);
			v.push_back(fount2[i+1]);
			a.push_back(1);
			b.push_back(sy2[i]+1);
			i++;
		}
	}
	
	for(int i=0; i<cnt4; i++){
		if(i == cnt4-1) continue;
		while(sy4[i+1]-sy4[i] == 2){
			u.push_back(fount4[i]);
			v.push_back(fount4[i+1]);
			a.push_back(5);
			b.push_back(sy4[i]+1);
			i++;
		}
	}
	
	for(int i=0; i<cnt2; i++){
		int temp = emf[sy2[i]];
		if(temp == 0) continue;
		if(temp == -1) temp = 0;
		if(i == fount4[temp] || u[fount2[i]] != u[fount4[temp]]) continue;
		u.push_back(i);
		v.push_back(fount4[temp]);
		a.push_back(3);
		b.push_back(sy2[i]-1);
	}
	
	int s = u.size();
	for(int i=0; i<s; i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs(u[0]);
	if(numofvis != n) return 0;
    build(u, v, a, b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 77 ms 12136 KB Output is correct
10 Correct 11 ms 5964 KB Output is correct
11 Correct 33 ms 8860 KB Output is correct
12 Correct 11 ms 6220 KB Output is correct
13 Correct 14 ms 6756 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 83 ms 12176 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 77 ms 12136 KB Output is correct
10 Correct 11 ms 5964 KB Output is correct
11 Correct 33 ms 8860 KB Output is correct
12 Correct 11 ms 6220 KB Output is correct
13 Correct 14 ms 6756 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 83 ms 12176 KB Output is correct
17 Incorrect 3 ms 4940 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 77 ms 12136 KB Output is correct
10 Correct 11 ms 5964 KB Output is correct
11 Correct 33 ms 8860 KB Output is correct
12 Correct 11 ms 6220 KB Output is correct
13 Correct 14 ms 6756 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 83 ms 12176 KB Output is correct
17 Incorrect 3 ms 4940 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 77 ms 12136 KB Output is correct
10 Correct 11 ms 5964 KB Output is correct
11 Correct 33 ms 8860 KB Output is correct
12 Correct 11 ms 6220 KB Output is correct
13 Correct 14 ms 6756 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 83 ms 12176 KB Output is correct
17 Incorrect 3 ms 4940 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 77 ms 12136 KB Output is correct
10 Correct 11 ms 5964 KB Output is correct
11 Correct 33 ms 8860 KB Output is correct
12 Correct 11 ms 6220 KB Output is correct
13 Correct 14 ms 6756 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 83 ms 12176 KB Output is correct
17 Runtime error 101 ms 27640 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 77 ms 12136 KB Output is correct
10 Correct 11 ms 5964 KB Output is correct
11 Correct 33 ms 8860 KB Output is correct
12 Correct 11 ms 6220 KB Output is correct
13 Correct 14 ms 6756 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 83 ms 12176 KB Output is correct
17 Incorrect 3 ms 4940 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -