제출 #141664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
141664		GioChkhaidze	Flood (IOI07_flood)	C++14	20 / 100	292 ms	20472 KiB

flood

#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]==X) { ko=1; return; } f[idxedge]=X;
	if (F[idxedge]) return ; F[idxedge]=1;
	st.erase(st.find({{x[b[idxedge]],y[a[idxedge]]},idxedge}));

	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;
		++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]);
}

컴파일 시 표준 에러 (stderr) 메시지

flood.cpp:47:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () { 
       ^
flood.cpp: In function 'int main()':
flood.cpp:80: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:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<ANS.size(); i++) 
                ~^~~~~~~~~~~
flood.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
flood.cpp:51: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:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
flood.cpp:56: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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 0 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9