Submission #1316549

#TimeUsernameProblemLanguageResultExecution timeMemory
1316549trinm01Flood (IOI07_flood)C++20
73 / 100
619 ms54508 KiB
#include<bits/stdc++.h>
using namespace std;
// #define int long long 
#define ll long long 
#define FOR(i, l, r) for(int i=l; i<=r; i++)
#define FOD(i, r, l) for(int i=r; i>=l; i--)
#define pii pair<int, int>
#define fi first
#define se second 
const int MAXN=1e5+5;

int n, m;
struct poin{
	int x, y;
}a[MAXN];
map<pii, int> ax2;

int hx[]={1, 0, -1, 0}, hy[]={0, 1, 0, -1};
pii tt[MAXN][5];

set<int> s;
multiset<pair<pii, int>> ss;
int vis[MAXN];
void dfs(int u){
	vis[u]=1;
	FOR(i, 0, 3){
		int v=tt[u][i].fi;
		if(!v) continue;
		if(s.find(ax2[{u, v}])==s.end()){	
			ss.insert({{a[u].x, a[u].y}, u});
			ss.insert({{a[v].x, a[v].y}, v});
			s.insert(ax2[{u, v}]);
		}
		if(vis[v]) continue;
		dfs(v);
	}
}

int vst[MAXN][5];

int chk[MAXN];
void tinh(){
	while(1){
		if(s.empty()) break;
		if(ss.empty()) break;
		int u=(*ss.begin()).se;
		int h=1;
		set<pii> hist;
		while(1){				
			// cout << u << ' ';
			int ok=1;
			FOR(ii, ((h-1)%4+4)%4, ((h-1)%4+4)%4+3){
				int i=ii%4;
				int v=tt[u][i].fi;
				int id=tt[u][i].se;
				// cout << v << ' ';
				if(v && s.find(id)!=s.end()){
					if(vst[u][i]){
						ok=1;
						break;
					}
					vst[u][i]=1;
					hist.insert({u, v});
					u=v;
					h=i;
					ok=0;
					break;
				}
			}
			// cout << '\n';
			if(ok) break;
		}
		
		int ok=1;
		for(auto [u, v]:hist){
			// cout << u << ' ' << v << '\n';
			int id=ax2[{u, v}];
			if(hist.find({v, u})==hist.end()){
				chk[id]=1;
			}
			if(s.find(id)!=s.end()){
				ss.erase(ss.find({{a[u].x, a[u].y}, u}));
				ss.erase(ss.find({{a[v].x, a[v].y}, v}));
				s.erase(s.find(id));
				ok=0;
			}
		}
		if(ok) break;
	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
//	freopen("test.txt", "r", stdin);
//	freopen("o1.out", "w", stdout);
	
	if(fopen(".inp", "r")){
		freopen(".inp", "r", stdin);
		freopen(".out", "w", stdout);
	}
	
	cin >> n;
	FOR(i, 1, n){
		int x, y;
		cin >> x >> y;
		a[i]={x, y};
	}
	cin >> m;
	FOR(i, 1, m){
		int u, v;
		cin >> u >> v;
		ax2[{u, v}]=i;
		ax2[{v, u}]=i;
		
		FOR(_, 0, 1){
			FOR(j, 0, 3){
				if((a[v].x-a[u].x)*hx[j]>0 || (a[v].y-a[u].y)*hy[j]>0){
					tt[u][j]={v, i};
					break;
				}
			}
			swap(u, v);
		}
	}
	
	FOR(i, 1, n){
		if(!vis[i]){
			s.clear();
			ss.clear();
			dfs(i);
			tinh();
		}
	}
	
	int ans=0;
	vector<int> res;
	FOR(i, 1, m){
		if(!chk[i]){
			ans++;
			res.push_back(i);
		}
	}
	
	cout << ans << '\n';
	for(auto x:res){
		cout << x << '\n';
	}
	
	return 0;
}

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:100:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |                 freopen(".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
flood.cpp:101:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |                 freopen(".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...