oj.uz

Submission #597445

# Submission time Handle Problem Language Result Execution time Memory
597445 2022-07-16T03:46:37 Z NekoRolly Flood (IOI07_flood) C++17
42 / 100
 149 ms 65536 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;
}

int n,m,n1,n2;
pii p[N];
int Ed[N][4];
vector<pii> adj[N*2];
Node a1[N*2],a2[N*2];
vector<Rango> LRs[N*10];
set<Rango> d;
deque<int> d2;
int dis[N*2];
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();
	for (int x=0; x<N*10; x++) LRs[x].clear();
	for (int j=0; j<n; j++){ auto [l, r, x, i] = a[j];
		LRs[x+1].push_back({l, r, i});
	}
	for (int x=0; x<N*10; x++) for (auto [l, r, i] : LRs[x]){
		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 26 ms 28500 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28548 KB Output is correct
2 Correct 25 ms 28528 KB Output is correct
3 Incorrect 22 ms 28552 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 24 ms 28444 KB Output is correct

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28528 KB Output is correct
2 Incorrect 24 ms 28556 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 22 ms 28500 KB Output is correct
2 Correct 23 ms 28528 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28532 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28628 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28540 KB Output is correct
2 Correct 23 ms 28612 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28540 KB Output is correct
2 Correct 23 ms 28648 KB Output is correct

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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

Subtask #12
0 / 9.0

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

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 95 ms 65536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 65536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -