oj.uz

Submission #134941

# Submission time Handle Problem Language Result Execution time Memory
134941 2019-07-23T13:03:23 Z wzy Land of the Rainbow Gold (APIO17_rainbow) C++11
11 / 100
 3000 ms 225760 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);
    // 			}
    // 		} 
    // 	}
    // }
    for(int i = ar ; i <= br ; i ++){
    	for(int j = ac ; j <= bc ;j ++){
    		if(!relabel[pii(i,j)]) relabel[pii(i,j)] = ++ cc;
    		T.fd(relabel[pii(i,j)] , river.count(pii(i,j)));
    	}
    }
    for(int i = ar ; i <= br ; i ++){
    	for(int j = ac ; j <= bc ;j ++){
    		for(int k = 0 ; k < 4 ; k ++){
    			int u = i + dx[k] , v = j + dy[k];
    			if(ar <= u && u <= br && ac <= v && v <= bc){
    				if(river.count(pii(u , v)) == river.count(pii(i,j))){
    					T.join(relabel[pii(u,v)], relabel[pii(i , j)] , river.count(pii(u,v)));
    				}
    			}
    		}
    	}
    }    

    return (T.get_c() );
}
// #define int int

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 376 KB Output is correct
2 Correct 1135 ms 928 KB Output is correct
3 Correct 2703 ms 1036 KB Output is correct
4 Correct 2678 ms 788 KB Output is correct
5 Correct 1252 ms 1144 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 508 KB Output is correct
11 Correct 2239 ms 888 KB Output is correct
12 Correct 2423 ms 860 KB Output is correct
13 Correct 1984 ms 896 KB Output is correct
14 Correct 2064 ms 1008 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Execution timed out 3099 ms 54172 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Execution timed out 3070 ms 225760 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 376 KB Output is correct
2 Correct 1135 ms 928 KB Output is correct
3 Correct 2703 ms 1036 KB Output is correct
4 Correct 2678 ms 788 KB Output is correct
5 Correct 1252 ms 1144 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 508 KB Output is correct
11 Correct 2239 ms 888 KB Output is correct
12 Correct 2423 ms 860 KB Output is correct
13 Correct 1984 ms 896 KB Output is correct
14 Correct 2064 ms 1008 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Execution timed out 3011 ms 89636 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 376 KB Output is correct
2 Correct 1135 ms 928 KB Output is correct
3 Correct 2703 ms 1036 KB Output is correct
4 Correct 2678 ms 788 KB Output is correct
5 Correct 1252 ms 1144 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 508 KB Output is correct
11 Correct 2239 ms 888 KB Output is correct
12 Correct 2423 ms 860 KB Output is correct
13 Correct 1984 ms 896 KB Output is correct
14 Correct 2064 ms 1008 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Execution timed out 3011 ms 89636 KB Time limit exceeded
19 Halted 0 ms 0 KB -