oj.uz

Submission #54327

# Submission time Handle Problem Language Result Execution time Memory
54327 2018-07-03T07:26:23 Z 윤교준(#1474) Flood (IOI07_flood) C++11
100 / 100
 348 ms 25752 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 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;

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 e : O) {
			if(djsf.uf(e*2) == djsf.uf(1)) continue;
			djs.uf(1, e*2);
			djsf.uf(1, e*2);
			//printf("SEX %d", e);
		}
	}
	{
		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 e : O) {
			if(djsf.uf(e*2) == djsf.uf(1)) continue;
			djs.uf(1, e*2);
			djsf.uf(1, e*2);
			//printf("SEX %d", e);
		}
	}

	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;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16724 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16872 KB Output is correct
2 Correct 15 ms 17052 KB Output is correct
3 Correct 15 ms 17052 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17052 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17052 KB Output is correct
2 Correct 19 ms 17052 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17052 KB Output is correct
2 Correct 16 ms 17052 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17084 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 17084 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17084 KB Output is correct
2 Correct 15 ms 17108 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17108 KB Output is correct
2 Correct 16 ms 17108 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18412 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 22428 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 22448 KB Output is correct
2 Correct 239 ms 24936 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 24936 KB Output is correct
2 Correct 269 ms 25752 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 25752 KB Output is correct
2 Correct 202 ms 25752 KB Output is correct