oj.uz

답안 #440663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440663 2021-07-02T17:19:26 Z antontsiorvas 분수 공원 (IOI21_parks) C++17
5 / 100
 124 ms 20980 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[fount4[i]]] = fount4[i]; 
//    emf[sy4[fount4[0]]] = -1;
    std::sort(&sy4[0],&sy4[cnt4]);
    for(int i=1; i<cnt4; i++) emf[sy4[i]] = i; 
    emf[sy4[0]] = -1;
    
    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[fount2[i]]];
		if(temp == 0) continue;
		if(temp == -1) temp = 0;
		u.push_back(fount2[i]);
		v.push_back(fount4[temp]);
		a.push_back(3);
		b.push_back(sy2[fount2[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

# 결과 실행 시간 메모리 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 4988 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 79 ms 12144 KB Output is correct
10 Correct 9 ms 5964 KB Output is correct
11 Correct 35 ms 8928 KB Output is correct
12 Correct 11 ms 6232 KB Output is correct
13 Correct 15 ms 6732 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 79 ms 12180 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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 4988 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 79 ms 12144 KB Output is correct
10 Correct 9 ms 5964 KB Output is correct
11 Correct 35 ms 8928 KB Output is correct
12 Correct 11 ms 6232 KB Output is correct
13 Correct 15 ms 6732 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 79 ms 12180 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Incorrect 3 ms 4940 KB Pair u[2]=1 @(2, 6) and v[2]=0 @(4, 4) does not form a valid edge (distance != 2)
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 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 4988 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 79 ms 12144 KB Output is correct
10 Correct 9 ms 5964 KB Output is correct
11 Correct 35 ms 8928 KB Output is correct
12 Correct 11 ms 6232 KB Output is correct
13 Correct 15 ms 6732 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 79 ms 12180 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Incorrect 3 ms 4940 KB Pair u[2]=1 @(2, 6) and v[2]=0 @(4, 4) does not form a valid edge (distance != 2)
19 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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 4988 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 79 ms 12144 KB Output is correct
10 Correct 9 ms 5964 KB Output is correct
11 Correct 35 ms 8928 KB Output is correct
12 Correct 11 ms 6232 KB Output is correct
13 Correct 15 ms 6732 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 79 ms 12180 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

# 결과 실행 시간 메모리 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 4988 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 79 ms 12144 KB Output is correct
10 Correct 9 ms 5964 KB Output is correct
11 Correct 35 ms 8928 KB Output is correct
12 Correct 11 ms 6232 KB Output is correct
13 Correct 15 ms 6732 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 79 ms 12180 KB Output is correct
17 Incorrect 124 ms 20980 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 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 4988 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 79 ms 12144 KB Output is correct
10 Correct 9 ms 5964 KB Output is correct
11 Correct 35 ms 8928 KB Output is correct
12 Correct 11 ms 6232 KB Output is correct
13 Correct 15 ms 6732 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 79 ms 12180 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Incorrect 3 ms 4940 KB Pair u[2]=1 @(2, 6) and v[2]=0 @(4, 4) does not form a valid edge (distance != 2)
19 Halted 0 ms 0 KB -