oj.uz

Submission #54351

# Submission time Handle Problem Language Result Execution time Memory
54351 2018-07-03T08:02:37 Z 윤교준(#1474) Flood (IOI07_flood) C++11
73 / 100
 497 ms 33048 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }

const int MAXN = 100005;
const int MAXK = 200005;
const int MX = 400005;

struct SEG {
    SEG() { init(); }
    int d[MX*3], dd[MX*3];
    void init() { fill(d, d+MX*3, -1); fill(dd, dd+MX*3, -1); }
    void upd(int i, int s, int e, int p, int q, int r) {
        if(q < p || e < p || q < s) return;
		upmax(dd[i], r);
		if(p <= s && e <= q) {
			upmax(d[i], r);
			return;
		}
		int m = (s+e)/2;
		upd(i*2, s, m, p, q, r);
		upd(i*2+1, m+1, e, p, q, r);
    }
	void upd(int s, int e, int x) { upd(1, 0, 400000, s, e, x); }
	int get(int i, int s, int e, int p, int q) {
		if(q < p || e < p || q < s) return -1;
		if(p <= s && e <= q) return dd[i];
		int m = (s+e)/2;
		return max({d[i], get(i*2, s, m, p, q), get(i*2+1, m+1, e, p, q)});
	}
	int get(int s, int e) { return get(1, 0, 400000, s, e); }
} seg;

struct DJS {
	DJS() { init(); }
	int ud[MAXK*2];
	void init() { iota(ud, ud+MAXK*2, 0); }
	int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
	void uf(int a, int b) { ud[uf(b)] = uf(a); }
} djs;

vector<int> G[MAXN], GD[MAXK*2];

int D[MAXK*2];
int A[MAXK], B[MAXK];
int X[MAXN], Y[MAXN];

vector<int> Ans;

int N, K;

int main() {
    //freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++)
		cin >> X[i] >> Y[i];
	cin >> K;
	for(int i = 1; i <= K; i++)
		cin >> A[i] >> B[i];

	for(int i = 1; i <= K; i++) {
		G[A[i]].pb(i);
		G[B[i]].pb(i);
	}

	for(int i = 1; i <= N; i++) {
		vector<int> &V = G[i];
		if(V.empty()) continue;

		vector<int> E;
		for(int e : V) {
			if(X[A[e]] != X[B[e]]) continue;
			if(min(Y[A[e]], Y[B[e]]) != Y[i]) continue;
			E.pb(e*2);
			E.pb(e*2+1);
		}
		for(int e : V) {
			if(Y[A[e]] != Y[B[e]]) continue;
			if(min(X[A[e]], X[B[e]]) != X[i]) continue;
			E.pb(e*2);
			E.pb(e*2+1);
		}
		for(int e : V) {
			if(X[A[e]] != X[B[e]]) continue;
			if(max(Y[A[e]], Y[B[e]]) != Y[i]) continue;
			E.pb(e*2+1);
			E.pb(e*2);
		}
		for(int e : V) {
			if(Y[A[e]] != Y[B[e]]) continue;
			if(max(X[A[e]], X[B[e]]) != X[i]) continue;
			E.pb(e*2+1);
			E.pb(e*2);
		}

        int j = i;
        if(!E.empty()) {
            for(int i = 1; i+1 < sz(E); i += 2) {
                djs.uf(E[i], E[i+1]);
                //printf("UF %d %d at %d\n", E[i], E[i+1], j);
            }
            djs.uf(E[0], E.back());
            //printf("UF %d %d at %d\n", E[0], E.back(), j);
        }
	}

	{
		vector<int> VX;
		vector<int> O;
		for(int i = 1; i <= K; i++) {
			if(X[A[i]] != X[B[i]]) continue;
			O.pb(i);
			if(Y[A[i]] > Y[B[i]]) swap(A[i], B[i]);
			VX.pb(Y[A[i]]);
			VX.pb(Y[B[i]]-1);
		}
		sort(allv(O), [&](int a, int b) {
			return X[A[a]] < X[A[b]];
		});
		sorv(VX); univ(VX);

		for(int oi = 0, e; oi < sz(O); oi++) {
			e = O[oi];
			if(Y[A[e]] > Y[B[e]]) swap(A[e], B[e]);
			int sy = (int)(lower_bound(allv(VX), Y[A[e]]) - VX.begin());
			int ey = (int)(lower_bound(allv(VX), Y[B[e]]-1) - VX.begin());
			int idx = seg.get(sy, ey);
			if(idx < 0) {
				djs.uf(1, e*2);
			} else {
			   // printf("e=%d, nxt=%d\n", e, O[idx]);
				djs.uf(e*2, O[idx]*2+1);
			}
			seg.upd(sy, ey, oi);
		}
	}
	{
		seg.init();
		vector<int> O, VX;
		for(int i = 1; i <= K; i++) {
			if(Y[A[i]] != Y[B[i]]) continue;
			O.pb(i);
			if(X[A[i]] > X[B[i]]) swap(A[i], B[i]);
			VX.pb(X[A[i]]);
			VX.pb(X[B[i]]-1);
		}
		sort(allv(O), [&](int a, int b) {
			return Y[A[a]] < Y[A[b]];
		});
		sorv(VX);
		univ(VX);

		for(int oi = 0, e; oi < sz(O); oi++) {
			e = O[oi];
			if(X[A[e]] > X[B[e]]) swap(A[e], B[e]);
			int sx = (int)(lower_bound(allv(VX), X[A[e]]) - VX.begin());
			int ex = (int)(lower_bound(allv(VX), X[B[e]]-1) - VX.begin());
			int idx = seg.get(sx, ex);
			if(idx < 0) {
				djs.uf(1, e*2+1);
			} else {
				djs.uf(e*2+1, O[idx]*2);
			}
			seg.upd(sx, ex, oi);
		}
	}

	for(int i = 1; i <= K; i++) {
        //printf("EDG %d : %d %d\n", i, djs.uf(i*2), djs.uf(i*2+1));
		if(djs.uf(i*2) == djs.uf(i*2+1)) continue;
		fg(GD, djs.uf(i*2), djs.uf(i*2+1));
	}

	{
		queue<int> PQ;

		fill(D, D+MAXK*2, INF);
		D[djs.uf(1)] = 0;
		PQ.push(djs.uf(1));

		for(int i, dst; !PQ.empty(); PQ.pop()) {
			i = PQ.front();
			dst = D[i] + 1;
			for(int v : GD[i]) {
				if(D[v] <= dst) continue;
				D[v] = dst;
				PQ.push(v);
			}
		}
	}

	for(int i = 1; i <= K; i++) {
		if(D[djs.uf(i*2)] != D[djs.uf(i*2+1)]) continue;
		Ans.pb(i);
	}

	printf("%d\n", sz(Ans));
	for(int v : Ans) printf("%d\n", v);

	return 0;
	for(int i = 1; i <= 2*K+1; i++)
        printf("%d : %d\n", i, D[i]);

	return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:110:13: warning: unused variable 'j' [-Wunused-variable]
         int j = i;
             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24696 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24812 KB Output is correct
2 Correct 27 ms 24812 KB Output is correct
3 Correct 28 ms 24812 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24840 KB Output is correct
2 Correct 25 ms 24864 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24864 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24912 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24912 KB Output is correct
2 Correct 25 ms 25068 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25068 KB Output is correct
2 Correct 25 ms 25068 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 26204 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 29772 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 30204 KB Output is correct
2 Runtime error 379 ms 32960 KB Memory limit exceeded

Subtask #13
0 / 9.0

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

Subtask #14
0 / 9.0

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