oj.uz

Submission #121318

# Submission time Handle Problem Language Result Execution time Memory
121318 2019-06-26T10:19:35 Z TadijaSebez Flood (IOI07_flood) C++11
100 / 100
 355 ms 14324 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
const int N=200050;
struct pt{ int x,y;pt(){}pt(int a, int b):x(a),y(b){}} P[N];
bool operator < (pt a, pt b){ return mp(a.x,a.y)<mp(b.x,b.y);}
int a[N],b[N],ty[N];
struct seg
{
	int id;
	seg(int x=0):id(x){}
	bool operator < (seg s) const
	{
		if(P[a[id]].x!=P[a[s.id]].x) return P[a[id]].x<P[a[s.id]].x;
		if(ty[id]!=ty[s.id]) return ty[id]<ty[s.id];
		return P[a[id]]<P[a[s.id]];
	}
};
set<seg> work;
pair<int,int> edge[N][4];
int cnt[N];
int go[4]={3,0,1,2};
int main()
{
	int n,w;
	scanf("%i",&n);
	for(int i=1;i<=n;i++) scanf("%i %i",&P[i].x,&P[i].y);
	scanf("%i",&w);
	for(int i=1;i<=w;i++)
	{
		scanf("%i %i",&a[i],&b[i]);
		if(P[b[i]]<P[a[i]]) swap(a[i],b[i]);
		if(P[a[i]].x==P[b[i]].x)
		{
			ty[i]=1;
			edge[a[i]][0]={i,b[i]};
			edge[b[i]][2]={i,a[i]};
		}
		else
		{
			ty[i]=2;
			edge[a[i]][1]={i,b[i]};
			edge[b[i]][3]={i,a[i]};
		}
		work.insert(seg(i));
	}
	while(work.size())
	{
		int x=work.begin()->id;
		int fir=a[x],sec=b[x];
		vector<int> was;
		int u=b[x],mod;
		if(ty[x]==1) mod=3;
		else mod=0;
		while(1)
		{
			int v;
			for(int i=0;i<4;i++)
			{
				int nm=(mod+i)%4;
				if(edge[u][nm].first)
				{
					cnt[edge[u][nm].first]++;
					was.pb(edge[u][nm].first);
					v=edge[u][nm].second;
					mod=go[nm];
					break;
				}
			}
			if(u==fir && v==sec) break;
			u=v;
		}
		sort(was.begin(),was.end());
		was.erase(unique(was.begin(),was.end()),was.end());
		for(int id:was)
		{
			if(ty[id]==1)
			{
				edge[a[id]][0]={0,0};
				edge[b[id]][2]={0,0};
			}
			else
			{
				edge[a[id]][1]={0,0};
				edge[b[id]][3]={0,0};
			}
			work.erase(seg(id));
		}
	}
	vector<int> ans;
	for(int i=1;i<=w;i++) if(cnt[i]==2) ans.pb(i);
	printf("%i\n",ans.size());
	for(int i:ans) printf("%i\n",i);
	return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:93:26: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%i\n",ans.size());
                ~~~~~~~~~~^
flood.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
flood.cpp:28:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&P[i].x,&P[i].y);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&w);
  ~~~~~^~~~~~~~~
flood.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&a[i],&b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
flood.cpp:71:18: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(u==fir && v==sec) break;
                 ~^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2808 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8920 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 9644 KB Output is correct
2 Correct 322 ms 14036 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 12064 KB Output is correct
2 Correct 355 ms 14324 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 13520 KB Output is correct
2 Correct 321 ms 12416 KB Output is correct