oj.uz

답안 #597733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
597733 2022-07-16T18:16:52 Z NekoRolly Flood (IOI07_flood) C++17
100 / 100
 374 ms 31776 KB 
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5+10;
const int inf = 1e9;

struct Node{
	int l,r,x,i;
};

struct Rango{
	int l,r,i;
};

bool operator<(Rango a,Rango b){
	return a.l != b.l ? a.l < b.l : a.i < b.i;
}

bool operator<(Node a,Node b){
	return a.x < b.x;
}

int n,m;
pii p[N];
int Ed[N][4];
vector<int> adj[N*4];
vector<Node> a1,a2;
set<Rango> d;
deque<int> d2;
int dis[N*4];
vector<int> ans;

int Id(int a,int b){
	if (p[a].ff == p[b].ff) return p[a].ss < p[b].ss ? 0 : 2;
	else return p[a].ff < p[b].ff ? 1 : 3;
}

void Add(int a,int b,int w=0){
	adj[a].push_back(b*(w?1:-1)), adj[b].push_back(a*(w?1:-1));
}

void new_line(int i,int a,int b){
	Ed[a][Id(a, b)] = Ed[b][Id(b, a)] = i;
	if (Id(a, b) == 0) a1.push_back({p[a].ss, p[b].ss, p[a].ff, i});
	if (Id(a, b) == 1) a2.push_back({p[a].ff, p[b].ff, p[a].ss, i});
	if (Id(a, b) == 2) a1.push_back({p[b].ss, p[a].ss, p[a].ff, i});
	if (Id(a, b) == 3) a2.push_back({p[b].ff, p[a].ff, p[a].ss, i});
}

void go(vector<Node> &v){ d.clear();
	sort(v.begin(), v.end());
	for (auto [l, r, x, i] : v){
		auto it = d.lower_bound({l, r, 0});
		if (d.size() && it != d.begin()) it--;
		if (it != d.end() && it->r <= l) it++;
		vector<Rango> d1;
		for (; it != d.end() && it->l < r; it++) d1.push_back(*it);
		for (Rango RL : d1) d.erase(RL);
		d.insert({l, r, i});
		for (Rango RL : d1){ Add(RL.i, i+m);
			if (RL.l < l) d.insert({RL.l, l, RL.i});
			if (r < RL.r) d.insert({r, RL.r, RL.i});
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;

	for (int i=1; i<=n; i++) cin >> p[i].ff >> p[i].ss;

	cin >> m; p[++n] = {-1, -1}, p[++n] = {-1, 1e6+1};
	p[++n] = {1e6+1, -1}, p[++n] = {1e6+1, 1e6+1};

	for (int i=1,a,b; i<=m; i++){ cin >> a >> b;
		new_line(i, a, b);
	}

	m += 4; new_line(m-3, n-3, n-2), new_line(m-2, n-3, n-1);
	new_line(m-1, n-2, n), new_line(m, n-1, n);

	for (int i=1; i<=m; i++) Add(i, i+m, 1);

	for (int i=1; i<=n; i++) for (int j=0,k; j<4; j++) if (Ed[i][j]){
		for (k = (j+1)%4; !Ed[i][k]; ) k = (k+1)%4;
		Add(Ed[i][j] + (j%3 ? m : 0), Ed[i][k] + (k%3 ? 0 : m));
	}

	go(a1), go(a2); d.clear();

	for (int i=1; i<=2*m; i++) dis[i] = inf;
	for (int u : {2*m-3, 2*m-2, m-1, m}){ d2.push_back(u); dis[u] = 0;}

	for (; d2.size(); ){ int u = d2.front(); d2.pop_front();
		for (int vw : adj[u]){ int w = vw > 0, v = abs(vw);
			if (dis[v] > dis[u] + w){ dis[v] = dis[u] + w;
				if (w) d2.push_back(v);
				else d2.push_front(v);
			}
		}
	}
/*
	for (int i=1; i<=2*m; i++){ cout << i << " -> ";
		for (auto [v, w] : adj[i]) if (!w)
			cout << v << " "; cout << "\n";
	}
	for (int i=1; i<=m; i++) cout << i << " -> " << dis[i] << " " << dis[i+m] << "\n";
*/
	for (int i=1; i<m-3; i++) if (dis[i] == dis[i+m]) ans.push_back(i);

	cout << ans.size() << "\n";
	for (int x : ans) cout << x << "\n";

	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9736 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct

Subtask #9
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 24592 KB Output is correct
2 Correct 353 ms 25720 KB Output is correct

Subtask #13
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 249 ms 25144 KB Output is correct
2 Correct 374 ms 31308 KB Output is correct

Subtask #14
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 272 ms 25516 KB Output is correct
2 Correct 240 ms 31776 KB Output is correct