oj.uz

Submission #440451

# Submission time Handle Problem Language Result Execution time Memory
440451 2021-07-02T09:57:09 Z antontsiorvas Fountain Parks (IOI21_parks) C++17
5 / 100
 149 ms 25832 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;
		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 4924 KB Output is correct
2 Correct 3 ms 4988 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 4992 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 4916 KB Output is correct
9 Correct 79 ms 12904 KB Output is correct
10 Correct 10 ms 5964 KB Output is correct
11 Correct 40 ms 9272 KB Output is correct
12 Correct 12 ms 6408 KB Output is correct
13 Correct 15 ms 7116 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 79 ms 12920 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4924 KB Output is correct
2 Correct 3 ms 4988 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 4992 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 4916 KB Output is correct
9 Correct 79 ms 12904 KB Output is correct
10 Correct 10 ms 5964 KB Output is correct
11 Correct 40 ms 9272 KB Output is correct
12 Correct 12 ms 6408 KB Output is correct
13 Correct 15 ms 7116 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 79 ms 12920 KB Output is correct
17 Incorrect 3 ms 4940 KB Pair u[2]=0 @(4, 4) and v[2]=0 @(4, 4) does not form a valid edge (distance != 2)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4924 KB Output is correct
2 Correct 3 ms 4988 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 4992 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 4916 KB Output is correct
9 Correct 79 ms 12904 KB Output is correct
10 Correct 10 ms 5964 KB Output is correct
11 Correct 40 ms 9272 KB Output is correct
12 Correct 12 ms 6408 KB Output is correct
13 Correct 15 ms 7116 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 79 ms 12920 KB Output is correct
17 Incorrect 3 ms 4940 KB Pair u[2]=0 @(4, 4) and v[2]=0 @(4, 4) does not form a valid edge (distance != 2)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4924 KB Output is correct
2 Correct 3 ms 4988 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 4992 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 4916 KB Output is correct
9 Correct 79 ms 12904 KB Output is correct
10 Correct 10 ms 5964 KB Output is correct
11 Correct 40 ms 9272 KB Output is correct
12 Correct 12 ms 6408 KB Output is correct
13 Correct 15 ms 7116 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 79 ms 12920 KB Output is correct
17 Incorrect 3 ms 5012 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 4924 KB Output is correct
2 Correct 3 ms 4988 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 4992 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 4916 KB Output is correct
9 Correct 79 ms 12904 KB Output is correct
10 Correct 10 ms 5964 KB Output is correct
11 Correct 40 ms 9272 KB Output is correct
12 Correct 12 ms 6408 KB Output is correct
13 Correct 15 ms 7116 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 79 ms 12920 KB Output is correct
17 Incorrect 149 ms 25832 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4924 KB Output is correct
2 Correct 3 ms 4988 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 4992 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 4916 KB Output is correct
9 Correct 79 ms 12904 KB Output is correct
10 Correct 10 ms 5964 KB Output is correct
11 Correct 40 ms 9272 KB Output is correct
12 Correct 12 ms 6408 KB Output is correct
13 Correct 15 ms 7116 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 79 ms 12920 KB Output is correct
17 Incorrect 3 ms 4940 KB Pair u[2]=0 @(4, 4) and v[2]=0 @(4, 4) does not form a valid edge (distance != 2)
18 Halted 0 ms 0 KB -