oj.uz

Submission #134938

# Submission time Handle Problem Language Result Execution time Memory
134938 2019-07-23T12:50:50 Z wzy Land of the Rainbow Gold (APIO17_rainbow) C++11
0 / 100
 1075 ms 45972 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
// V - E + F = 1 + C  ? V - E + F = 3 - C
set<pii> river;
set<pii> fc;
map<pii, int> relabel;
int cc = 0;
class dsu{
public:
 	int fd(int x , bool isr){
 		if(!pai.count(x)){
 			peso[x] = 1;
 			if(!isr)
 			c++;
 			return pai[x] = x;
 		}
 		return pai[x] == x ? x : pai[x] = fd(pai[x] , isr);
 	}
 	void join(int u , int v , bool isr){
 		if(fd(u,isr) == fd(v,isr)) return;
 		u = fd(u,isr) , v = fd(v,isr);
 		if(!isr)
 		c--;
 		if(peso[u] > peso[v]) swap(u,v);
 		pai[u] = v , peso[v] += peso[u];
 	}
 	int get_c(){
 		return c;
 	}
private:
	map<int,int> pai, peso;
	int c = 0;
};
int RR , CC;
void init(int R, int C, int sr, int sc, int M, char *S) {
	river.insert(pii(sr , sc));
	for(int i = 0 ; i < M ; i ++){
		if(S[i] == 'N') sr--;
		if(S[i] == 'S') sr++;
		if(S[i] == 'E') sc++;
		if(S[i] == 'W') sc --;
		river.insert(pii(sr , sc));
		if(!relabel.count(pii(sr , sc))){
			relabel[pii(sr,sc)] = ++ cc;
		}
 	}
 	RR = R , CC = C;
}
int dx[4] = {0 , 1 , 0 , -1};
int dy[4] = {1 , 0 , -1 , 0};

int colour(int ar, int ac, int br, int bc) {
    dsu T;
    set<pii> parte;
    fc.clear();
    for(auto w : river){
    	if(ar <= w.F && w.F <= br && ac <= w.S && w.S <= bc){
    		T.fd(relabel[w] , 1);
    		parte.insert(w);
    	}
    }
    for(auto w : parte){
    	for(int j = 0 ; j < 4 ; j ++){
    		int u = w.F + dx[j] , v = w.S + dy[j];
    		if(ar <= u && u <= br && ac <= v && v <= bc){
    			if(!relabel[pii(u,v)]){
    				relabel[pii(u,v)] = ++cc;
    			}
    			if(parte.count(pii(u,v))) T.join(relabel[pii(u,v)] , relabel[w] , 1);
    			else{
    				T.fd(relabel[pii(u,v)] , 0);
    				fc.insert(pii(u,v));
    			}
    		}
    	}
    }
    for(auto w : fc){
    	for(int j = 0 ; j < 4 ; j++){
    		int u = w.F + dx[j] , v = w.S + dy[j];
    		if(ar <= u && u <= br && ac <= v && v <= bc){
    			if(fc.count(pii(u,v))){
    				T.join(relabel[pii(u,v)] , relabel[w] , 0);
    			}
    		} 
    	}
    }

    return (T.get_c() + (parte.size() == 0 ? 1 : 0));
}
// #define int int

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1034 ms 39104 KB Output is correct
3 Correct 1033 ms 38992 KB Output is correct
4 Incorrect 1075 ms 45972 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -