oj.uz

Submission #161118

# Submission time Handle Problem Language Result Execution time Memory
161118 2019-10-31T14:49:19 Z GioChkhaidze Flood (IOI07_flood) C++14
20 / 100
 343 ms 20996 KB 
#include <bits/stdc++.h>

#define Left     if (L[idx].F)  { Dfs(L[idx].S.F,L[idx].S.S,0); L[idx].F=0,R[L[idx].S.F].F=0; if (ko) return ; }
#define Right    if (R[idx].F)  { Dfs(R[idx].S.F,R[idx].S.S,2); R[idx].F=0,L[R[idx].S.F].F=0; if (ko) return ;  }
#define Up 	     if (U[idx].F)  { Dfs(U[idx].S.F,U[idx].S.S,3); U[idx].F=0,D[U[idx].S.F].F=0; if (ko) return ; }
#define Down 	 if (D[idx].F)  { Dfs(D[idx].S.F,D[idx].S.S,1); D[idx].F=0,U[D[idx].S.F].F=0; if (ko) return ; }

#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 > > U[N],L[N],D[N],R[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[a[idxedge]],y[b[idxedge]]},idxedge}));
 
	if (p==3) { Left Up Right ANS.push_back(idxedge); } // qvevidan 
		else
	if (p==2) {  Up Right Down ANS.push_back(idxedge); } // marcxnidan
		else
	if (p==1) { Right Down Left ANS.push_back(idxedge);	}  // zevidan
		else
	if (!p) { Down Left Up ANS.push_back(idxedge); } // marjvnidan
}
 
main () { 
	scanf("%d",&n);
	
	for (int i=1; i<=n; i++)
		scanf("%d %d",&x[i],&y[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]);

		int I=a[i],J=b[i];

		if (x[I]==x[J]) D[J].F=1,D[J].S.F=I,D[J].S.S=i,U[I].F=1,U[I].S.F=J,U[I].S.S=i;
				   else R[J].F=1,R[J].S.F=I,R[J].S.S=i,L[I].F=1,L[I].S.F=J,L[I].S.S=i;	
		
		st.insert({{x[I],y[J]},i});
	}
	
	while (st.size()) {
		int stedge=(*st.rbegin()).S;
		ko=0,++X;
		
		if (x[a[stedge]]==x[b[stedge]]) Dfs(a[stedge],stedge,1);	
								   else Dfs(a[stedge],stedge,2);
	}
	
	printf("%d\n",ANS.size());
	for (int i=0; i<ANS.size(); i++) 
		printf("%d\n",ANS[i]);
}

Compilation message

flood.cpp:33:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () { 
       ^
flood.cpp: In function 'int main()':
flood.cpp:63: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:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<ANS.size(); i++) 
                ~^~~~~~~~~~~
flood.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
flood.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x[i],&y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
flood.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
flood.cpp:42: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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 3512 KB Output isn't correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 12664 KB Output isn't correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 12412 KB Output is correct
2 Incorrect 343 ms 20996 KB Output isn't correct

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 259 ms 16008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 298 ms 17700 KB Output isn't correct
2 Halted 0 ms 0 KB -