oj.uz

Submission #351163

# Submission time Handle Problem Language Result Execution time Memory
351163 2021-01-19T13:14:54 Z minoum Flood (IOI07_flood) C++17
29 / 100
 351 ms 35944 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 5e5 + 10;

int n, m, h[MAXN], dw[MAXN], up[MAXN], lf[MAXN], ri[MAXN], allw[MAXN];
vector <pair<int,int>> pt, adj[MAXN], ofo, amo, w; //ofo=y,amo=x
bool mark[MAXN];

inline void addedge(){
	for(int i = 0; i < n; i++){
		if(allw[i] <= 1) continue;
		if(up[i] != -1 && ri[i] != -1){
			adj[up[i]*2].push_back({ri[i]*2+1,0});
			adj[ri[i]*2+1].push_back({up[i]*2,0});
			if(dw[i]==-1&&lf[i]==-1){
				adj[up[i]*2+1].push_back({ri[i]*2,0});
				adj[ri[i]*2].push_back({up[i]*2+1,0});
			}
		}
		if(dw[i] != -1 && ri[i] != -1){
			adj[dw[i]*2].push_back({ri[i]*2,0});
			adj[ri[i]*2].push_back({dw[i]*2,0});
			if(lf[i]==-1 && up[i]==-1){
				adj[dw[i]*2+1].push_back({ri[i]*2+1,0});
				adj[ri[i]*2+1].push_back({dw[i]*2+1,0});
			}
		}
		if(dw[i] != -1 && lf[i] != -1){
			adj[dw[i]*2+1].push_back({lf[i]*2,0});
			adj[lf[i]*2].push_back({dw[i]*2+1,0});
			if(up[i]==-1&&ri[i]==-1){
				adj[dw[i]*2].push_back({lf[i]*2+1,0});
				adj[lf[i]*2+1].push_back({dw[i]*2,0});
			}
		}
		if(up[i] != -1 && lf[i] != -1){
			adj[up[i]*2+1].push_back({lf[i]*2+1,0});
			adj[lf[i]*2+1].push_back({up[i]*2+1,0});
			if(dw[i]==-1&&ri[i]==-1){
				adj[up[i]*2].push_back({lf[i]*2,0});
				adj[lf[i]*2].push_back({up[i]*2,0});
			}
		}
		if(up[i] != -1 && dw[i] != -1){
			if(ri[i] == -1){
				adj[up[i]*2].push_back({dw[i]*2,0});
				adj[dw[i]*2].push_back({up[i]*2,0});
			}
			if(lf[i] == -1){
				adj[up[i]*2+1].push_back({dw[i]*2+1,0});
				adj[dw[i]*2+1].push_back({up[i]*2+1,0});
			}
		}
		if(ri[i] != -1 && lf[i] != -1){
			if(dw[i] == -1){
				adj[ri[i]*2].push_back({lf[i]*2,0});
				adj[lf[i]*2].push_back({ri[i]*2,0});
			}
			if(up[i] == -1){
				adj[ri[i]*2+1].push_back({ri[i]*2+1,0});
				adj[lf[i]*2+1].push_back({lf[i]*2+1,0});
			}
		}
	}
	for(int i = 0; i < m; i++){
		int t = 1;
		if(allw[w[i].first]==1 || allw[w[i].second]==1) t = 0;
		adj[i*2].push_back({i*2+1,t});
		adj[i*2+1].push_back({i*2,t});
	}
	return;
}

inline void bfs(int r){
	mark[r] = true; h[r] = 0;
	deque <int> q;
	q.push_back(r);
	while(!q.empty()){
		int v = q.front(); q.pop_front(); mark[v] = true;
		for(auto i: adj[v]){
			int u = i.first, ww = i.second;
			if(h[u] <= h[v]+ww) continue;
			h[u] = h[v]+ww;
			if(ww == 0) q.push_front(u);
			else q.push_back(u); 
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for(int i = 0; i < MAXN; i++) h[i] = INT_MAX;
	cin >> n;
	for(int i = 0; i < n; i++){
		int xx,yy;
		cin >> xx >> yy;
		pt.push_back({xx,yy});
		dw[i] = up[i] = lf[i] = ri[i] = -1;
	}
	cin >> m;
	for(int i = 0; i < m; i++){
		int u, v, t = 0;
		cin >> u >> v; u--; v--;
		if(pt[u].first==pt[v].first){
			t = 1;
			amo.push_back({pt[u].first,i});
			if(pt[u].second > pt[v].second) swap(u,v);
			dw[u] = i; up[v] = i;
		} 
		else{
			ofo.push_back({pt[u].second,i});
			if(pt[u].first > pt[v].first) swap(u,v);
			ri[u] = i; lf[v] = i;
		}
		allw[u]++; allw[v]++;
		w.push_back({u,v});
	}
	addedge();
	sort(ofo.begin(), ofo.end());
	sort(amo.begin(), amo.end());
	for(auto i: ofo)
		if(!mark[i.second*2]) bfs(i.second*2+1);
	for(auto i: amo)
		if(!mark[i.second*2]) bfs(i.second*2+1);
	vector <int> ans;
	for(int i = 0; i < m; i++)
		if(h[i*2] == h[i*2+1]) ans.push_back(i);
	cout << (int)ans.size() << '\n';
	for(auto i: ans) cout << i+1 <<'\n';
	return 0; 
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:107:13: warning: variable 't' set but not used [-Wunused-but-set-variable]
  107 |   int u, v, t = 0;
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14060 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14060 KB Output is correct
2 Correct 11 ms 14060 KB Output is correct
3 Incorrect 11 ms 14060 KB Output isn't correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14060 KB Output is correct
2 Incorrect 12 ms 14188 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14060 KB Output is correct
2 Correct 11 ms 14060 KB Output is correct

Subtask #6
0 / 3.0

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

Subtask #7
0 / 3.0

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

Subtask #8
0 / 3.0

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

Subtask #9
0 / 3.0

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

Subtask #10
0 / 9.0

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

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 26024 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 26856 KB Output is correct
2 Runtime error 351 ms 35944 KB Memory limit exceeded

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 32772 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 315 ms 35748 KB Memory limit exceeded
2 Halted 0 ms 0 KB -