Submission #121318

#	Time	Username	Problem	Language	Result	Execution time	Memory
121318		TadijaSebez	Flood (IOI07_flood)	C++11	100 / 100	355 ms	14324 KiB

flood

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9