oj.uz

Submission #597450

# Submission time Handle Problem Language Result Execution time Memory
597450 2022-07-16T04:13:30 Z NekoRolly Flood (IOI07_flood) C++17
60 / 100
 343 ms 35040 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;
}

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

int n,m,n1,n2;
pii p[N];
int Ed[N][4];
vector<pii> adj[N*4];
Node a1[N*4],a2[N*4];
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}), adj[b].push_back({a, w});
}

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[n1++] = {p[a].ss, p[b].ss, p[a].ff, i};
	if (Id(a, b) == 1) a2[n2++] = {p[a].ff, p[b].ff, p[a].ss, i};
	if (Id(a, b) == 2) a1[n1++] = {p[b].ss, p[a].ss, p[a].ff, i};
	if (Id(a, b) == 3) a2[n2++] = {p[b].ff, p[a].ff, p[a].ss, i};
}

void go(Node a[],int n){ d.clear();
	sort(a, a+n);
	for (int id=0; id<n; id++){ auto [l, r, x, i] = a[id];
		auto it = d.upper_bound({l, r, i});
		if (d.size() && it != d.begin()){ it--;
			if (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++){
		if (Ed[i][0] && Ed[i][1]) Add(Ed[i][0], Ed[i][1]);
		if (Ed[i][1] && Ed[i][2]) Add(Ed[i][1]+m, Ed[i][2]);
		if (Ed[i][2] && Ed[i][3]) Add(Ed[i][2]+m, Ed[i][3]+m);
		if (Ed[i][3] && Ed[i][0]) Add(Ed[i][3], Ed[i][0]+m);
	}

	go(a1, n1), go(a2, n2);

	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 (auto [v, w] : adj[u]) 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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9696 KB Output is correct
3 Incorrect 5 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9696 KB Output is correct

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9784 KB Output is correct
2 Incorrect 5 ms 9868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9692 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9744 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13756 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 25532 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 28412 KB Output is correct
2 Runtime error 343 ms 35040 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

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

Subtask #14
0 / 9.0

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