oj.uz

Submission #141667

# Submission time Handle Problem Language Result Execution time Memory
141667 2019-08-08T17:38:29 Z GioChkhaidze Flood (IOI07_flood) C++14
20 / 100
 202 ms 32592 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]==X) { ko=1; return; } f[idxedge]=X;
	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); Left[idx].F=0,Right[Left[idx].S.F].F=0; if (ko) return ; }
		if (Up[idx].F)  { Dfs(Up[idx].S.F,Up[idx].S.S,3); Up[idx].F=0,Down[Up[idx].S.F].F=0; if (ko) return ; }
		if (Right[idx].F)  { Dfs(Right[idx].S.F,Right[idx].S.S,2); Right[idx].F=0,Left[Right[idx].S.F].F=0; 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); Up[idx].F=0,Down[Up[idx].S.F].F=0; if (ko) return ; }
		if (Right[idx].F)  { Dfs(Right[idx].S.F,Right[idx].S.S,2); Right[idx].F=0,Left[Right[idx].S.F].F=0; if (ko) return ; }
		if (Down[idx].F)  { Dfs(Down[idx].S.F,Down[idx].S.S,1); Down[idx].F=0,Up[Down[idx].S.F].F=0; 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); Right[idx].F=0,Left[Right[idx].S.F].F=0; if (ko) return ; }
		if (Down[idx].F)  { Dfs(Down[idx].S.F,Down[idx].S.S,1); Down[idx].F=0,Up[Down[idx].S.F].F=0; if (ko) return ; }
		if (Left[idx].F)  { Dfs(Left[idx].S.F,Left[idx].S.S,0); Left[idx].F=0,Right[Left[idx].S.F].F=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); Down[idx].F=0,Up[Down[idx].S.F].F=0; if (ko) return ; }
		if (Left[idx].F)  { Dfs(Left[idx].S.F,Left[idx].S.S,0); Left[idx].F=0,Right[Left[idx].S.F].F=0; if (ko) return ; }
		if (Up[idx].F)  { Dfs(Up[idx].S.F,Up[idx].S.S,3); Up[idx].F=0,Down[Up[idx].S.F].F=0; 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]);
}

Compilation message

flood.cpp:46:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () { 
       ^
flood.cpp: In function 'int main()':
flood.cpp:79: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:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<ANS.size(); i++) 
                ~^~~~~~~~~~~
flood.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
flood.cpp:50: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:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
flood.cpp:55: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 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)

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 Runtime error 6 ms 708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 6520 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 21596 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #12
0 / 9.0

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

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 166 ms 29424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 32592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -