oj.uz

답안 #351177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
351177 2021-01-19T14:08:23 Z minoum Flood (IOI07_flood) C++17
64 / 100
 509 ms 51516 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, all[MAXN]; //ofo=y,amo=x

inline void addedge(){
	for(int i = 0; i < n; i++){
		if(all[i].empty()) continue;
		sort(all[i].begin(), all[i].end()); all[i].push_back(all[i][0]);
		/*cout << "i:" << i+1 << '\n';
		for(auto j: all[i]) cout << j.first << ":" << j.second << "  ";
		cout << endl << endl;*/
		for(int j = 0; j < (int)all[i].size()-1; j++){
			int id = all[i][j].second, di = all[i][j].first, id2 = all[i][j+1].second, di2 = all[i][j+1].first;
			int t1 = (di==3||di==2), t2 = (di2==3||di2==2); //0->{1,0}  1->{3,2}
			if(t1 && !t2){
				adj[id].push_back({id2,0});
				adj[id2].push_back({id,0});
			}
			if(t1 && t2){
				adj[id].push_back({id2+m,0});
				adj[id2+m].push_back({id,0});
			}
			if(!t1 && !t2){
				adj[id+m].push_back({id2,0});
				adj[id2].push_back({id+m,0});
			}
			if(!t1 && t2){
				adj[id+m].push_back({id2+m,0});
				adj[id2+m].push_back({id+m,0});
			}
		}
	}
	for(int i = 0; i < m; i++){
		adj[i].push_back({i+m,1});
		adj[i+m].push_back({i,1});
	}
	return;
}

inline void slv(int r){
	set <pair<int,int>> st; h[r] = 0;
	st.insert({0,r});
	while(!st.empty()){
		int v = st.begin()->second; st.erase(*st.begin());
		for(auto i: adj[v]){
			int u = i.first, ww = i.second;
			if(h[u] > h[v]+ww){
				st.erase({h[u],u});
				h[u] = h[v]+ww;
				st.insert({h[u],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;
		cin >> u >> v; u--; v--;
		if(pt[u].first==pt[v].first){
			amo.push_back({pt[u].first,i});
			if(pt[u].second > pt[v].second) swap(u,v);
//			dw[u] = i; up[v] = i;
			all[u].push_back({2,i});
			all[v].push_back({0,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;
			all[u].push_back({1,i});
			all[v].push_back({3,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(h[i.second] >= INT_MAX) slv(i.second);
	for(auto i: amo)
		if(h[i.second] >= INT_MAX) slv(i.second);
	vector <int> ans;
	for(int i = 0; i < m; i++)
		if(h[i] == h[i+m]) ans.push_back(i);
	cout << (int)ans.size() << '\n';
	for(auto i: ans) cout << i+1 <<'\n';
	return 0; 
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 25836 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 25836 KB Output is correct
2 Correct 16 ms 25836 KB Output is correct
3 Correct 16 ms 25836 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 25836 KB Output is correct

Subtask #4
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 25836 KB Output is correct
2 Correct 19 ms 25964 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 25836 KB Output is correct
2 Correct 17 ms 25856 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 25836 KB Output is correct

Subtask #7
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 25836 KB Output is correct

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 25884 KB Output is correct
2 Correct 18 ms 25964 KB Output is correct

Subtask #9
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 25856 KB Output is correct
2 Correct 19 ms 25984 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 30064 KB Output is correct

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 154 ms 42344 KB Memory limit exceeded

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 121 ms 42472 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 442 ms 48468 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 509 ms 51516 KB Memory limit exceeded
2 Halted 0 ms 0 KB -