oj.uz

답안 #141601

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
141601 2019-08-08T13:57:27 Z GioChkhaidze Flood (IOI07_flood) C++14
10 / 100
 304 ms 17596 KB 
#include <bits/stdc++.h>
#include <iostream>
#define F first
#define S second
using namespace std;
const int N=200005;
int n,m,ko,X;
int x[N],y[N],a[N],b[N],f[N],F[N];
pair < int , pair < int , int > > Up[N],Left[N],Down[N],Right[N];
vector < int >  ANS;
set <pair < pair < int , int > , int > > st;

void Dfs (int idx,int idxedge,int p) {
	if (F[idxedge]) return ;
	
	st.erase(st.find({{x[b[idxedge]],y[a[idxedge]]},idxedge}));
	F[idxedge]=1;
	if (f[idx]==X) { ko=1; return; }
	f[idx]=X;
	
	if (p==3) {
		if (Left[idx].F)  { Dfs(Left[idx].S.F,Left[idx].S.S,0); if (ko) return ; }
		if (Up[idx].F)  { Dfs(Up[idx].S.F,Up[idx].S.S,3); if (ko) return ; }
		if (Right[idx].F)  { Dfs(Right[idx].S.F,Right[idx].S.S,2); if (ko) return ;  }
		ANS.push_back(idxedge);
	}
		else
	if (p==2) {
		if (Up[idx].F)  { Dfs(Up[idx].S.F,Up[idx].S.S,3); if (ko) return ; }
		if (Right[idx].F)  { Dfs(Right[idx].S.F,Right[idx].S.S,2); if (ko) return ; }
		if (Down[idx].F)  { Dfs(Down[idx].S.F,Down[idx].S.S,1); if (ko) return ; }
		ANS.push_back(idxedge);
	}
		else
	if (p==1) {
		if (Right[idx].F)  { Dfs(Right[idx].S.F,Right[idx].S.S,2); if (ko) return ; }
		if (Down[idx].F)  { Dfs(Down[idx].S.F,Down[idx].S.S,1); if (ko) return ; }
		if (Left[idx].F)  { Dfs(Left[idx].S.F,Left[idx].S.S,0); if (ko) return ; }
		ANS.push_back(idxedge);
	}
		else
	if (!p) {
		if (Down[idx].F)  { Dfs(Down[idx].S.F,Down[idx].S.S,1); if (ko) return ; }
		if (Left[idx].F)  { Dfs(Left[idx].S.F,Left[idx].S.S,0); if (ko) return ; }
		if (Up[idx].F)  { Dfs(Up[idx].S.F,Up[idx].S.S,3); if (ko) return ; }
		ANS.push_back(idxedge);
	}
}

main () { 
	scanf("%d",&n);
	
	for (int i=1; i<=n; i++)
		scanf("%d %d",&y[i],&x[i]);

	scanf("%d",&m);
	
	for (int i=1; i<=m; i++) {
		scanf("%d %d",&a[i],&b[i]);
		
		if (y[a[i]]>y[b[i]]) swap(a[i],b[i]);
		if (x[a[i]]<x[b[i]]) swap(a[i],b[i]);
		
		if (x[a[i]]==x[b[i]]) {
			Left[b[i]].F=1,Left[b[i]].S.F=a[i],Left[b[i]].S.S=i;
			Right[a[i]].F=1,Right[a[i]].S.F=b[i],Right[a[i]].S.S=i;
		}
			else {
			Up[b[i]].F=1,Up[b[i]].S.F=a[i],Up[b[i]].S.S=i;
			Down[a[i]].F=1,Down[a[i]].S.F=b[i],Down[a[i]].S.S=i;	
		}
		st.insert({{x[b[i]],y[a[i]]},i});
	}
	
	while (st.size()) {
		int stedge=(*st.begin()).S;
		ko=0;
		f[b[stedge]]=++X;
		if (x[a[stedge]]==x[b[stedge]]) Dfs(a[stedge],stedge,0);	
								   else Dfs(a[stedge],stedge,3);
	}
	
	printf("%d\n",ANS.size());
	
	for (int i=0; i<ANS.size(); i++) 
		printf("%d\n",ANS[i]);
}

Compilation message

flood.cpp:50:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () { 
       ^
flood.cpp: In function 'int main()':
flood.cpp:83:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n",ANS.size());
                ~~~~~~~~~~^
flood.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<ANS.size(); i++) 
                ~^~~~~~~~~~~
flood.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
flood.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&y[i],&x[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
flood.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
flood.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i],&b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 4 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct

Subtask #6
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #7
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 3448 KB Output isn't correct

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 12472 KB Output isn't correct

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 111 ms 12404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 255 ms 15880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 304 ms 17596 KB Output isn't correct
2 Halted 0 ms 0 KB -