oj.uz

Submission #54349

# Submission time Handle Problem Language Result Execution time Memory
54349 2018-07-03T07:56:56 Z 윤교준(#1474) Flood (IOI07_flood) C++11
0 / 100
 183 ms 33792 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 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 = 1048576;

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, 1000000, 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, 1000000, 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, djsf;

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]);
                djsf.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());
            djsf.uf(E[0], E.back());
            //printf("UF %d %d at %d\n", E[0], E.back(), j);
        }
	}

	for(int i = 1; i <= K; i++)
		djsf.uf(i*2, i*2+1);

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

		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 idx = seg.get(Y[A[e]], Y[B[e]]-1);
			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(Y[A[e]], Y[B[e]]-1, oi);
		}
	}
	{
		seg.init();
		vector<int> O;
		for(int i = 1; i <= K; i++) {
			if(Y[A[i]] != Y[B[i]]) continue;
			O.pb(i);
		}
		sort(allv(O), [&](int a, int b) {
			return Y[A[a]] < Y[A[b]];
		});

		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 idx = seg.get(X[A[e]], X[B[e]]-1);
			if(idx < 0) {
				djs.uf(1, e*2+1);
			} else {
				djs.uf(e*2+1, O[idx]*2);
			}
			seg.upd(X[A[e]], X[B[e]]-1, 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:109:13: warning: unused variable 'j' [-Wunused-variable]
         int j = i;
             ^
flood.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 123 ms 33792 KB Memory limit exceeded

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 124 ms 33792 KB Memory limit exceeded

Subtask #4
0 / 3.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 143 ms 33792 KB Memory limit exceeded

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 152 ms 33792 KB Memory limit exceeded

Subtask #8
0 / 3.0

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

Subtask #9
0 / 3.0

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

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 154 ms 33792 KB Memory limit exceeded

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 151 ms 33792 KB Memory limit exceeded

Subtask #12
0 / 9.0

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

Subtask #13
0 / 9.0

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

Subtask #14
0 / 9.0

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