oj.uz

답안 #894882

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894882 2023-12-29T07:16:13 Z Jawad_Akbar_JJ 분수 공원 (IOI21_parks) C++17
0 / 100
 1 ms 348 KB 
 
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
 
 
 
 
 
 
 
 
 
 
#include "parks.h"
#include <cstdio>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
 
 
 
 
 
 
 
 
 
const int N = 200000 + 10;
 
int seen[10][N];
int seen2[10][N];
int used[12][N];
 
int sn =  0;
 
vector<pair<int,int>> d = {{0,2},{2,0},{-2,0},{0,-2}};
 
vector<int> a,b,X,Y;
vector<pair<int,int>> up,nup;
 
void dfs(int i,int j){
	seen2[i][j] = true;
	sn++;
	for (auto [x,y] : d){
		int ni = i + x;
		int nj = j + y;
		if (!seen[ni][nj] or seen2[ni][nj])
			continue;
		if (i==ni and i==4)
			up.push_back({seen[i][j]-1,seen[ni][nj]-1});
		else
			nup.push_back({seen[i][j]-1,seen[ni][nj]-1});
		dfs(ni,nj);
	}
}
 
void dfs2(int i,int j){
	if (seen2[i][j])
		return;
	seen2[i][j] = true;
	sn++;
	int ni = i;
	int nj = j + 2;
	if (!seen[ni][nj] or seen2[ni][nj])
		return;
	if (i==ni and i==4)
		up.push_back({seen[i][j]-1,seen[ni][nj]-1});
	else
		nup.push_back({seen[i][j]-1,seen[ni][nj]-1});
	dfs2(ni,nj);
}
 
pair<int,int> det(int x1,int y1,int x2,int y2){
	if (x1 == x2){
		if (y1>y2)
			swap(y1,y2);
		if (x1 == 2)
			return {1,y1+1};
		if (x1 == 6)
			return {7,y1+1};
		if (used[3][y1-1] or used[3][y2 + 1])
			return {5,y1 + 1};
		return {3,y1 + 1};
	}
	if (x1>x2)
		swap(x1,x2);
 
	if (used[x1+1][y1-1])
		return {x1+1,y1+1};
	return {x1+1,y1-1};
}
 
int construct_roads(vector<int> x,vector<int> y){
	int n = x.size();
	int mny = 1e7,k;
	for (int i=0;i<n;i++){
		if (x[i]==2 or x[i]==6)
			dfs2(x[i],y[i]);
	}
 
	for (int i=0;i<n;i++){
		if (!seen2[x[i]][y[i]])
			dfs(x[i],y[i]);
	}
 
	dfs(k,mny);
 
	if (sn!=n)
		return 0;
 
	sort(begin(up),end(up));
	for (auto [i,j] : up){
		auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
		used[ii][jj] = true;
		a.push_back(i);
		b.push_back(j);
		X.push_back(ii);
		Y.push_back(jj);
	}
	for (auto [i,j] : nup){
		auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
		used[ii][jj] = true;
		a.push_back(i);
		b.push_back(j);
		X.push_back(ii);
		Y.push_back(jj);
	}
 
	build(a,b,X,Y);
	return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:111:5: warning: 'k' is used uninitialized in this function [-Wuninitialized]
  111 |  dfs(k,mny);
      |  ~~~^~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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