Submission #597452

#	Time	Username	Problem	Language	Result	Execution time	Memory
597452		NekoRolly	Flood (IOI07_flood)	C++17	60 / 100	313 ms	32420 KiB

flood

#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;
pii p[N];
int Ed[N][4];
vector<pii> 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}), 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.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.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), 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 (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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9