Submission #135099

#	Time	Username	Problem	Language	Result	Execution time	Memory
135099		wzy	Land of the Rainbow Gold (APIO17_rainbow)	C++11	0 / 100	3022 ms	51156 KiB

rainbow

#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:
    void clear_T(){
        pai.clear() , peso.clear() , c = 0 ;
    }
 	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 dx[4] = {0 , 1 , 0 , -1};
int dy[4] = {1 , 0 , -1 , 0};
int RR , CC;
int sum[2][200005];
int tudo[200005];
void init(int R, int C, int sr, int sc, int M, char *S) {
    river.insert(pii(sr , sc));
    tudo[0] = 0;
    sum[0][0] = 0;
    sum[1][0] = 0;
    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;
        }
    }
    dsu T;
    for(int j = 1 ; j <= C; j ++){
        for(int i = 1; i <= R ; i ++){
            if(!relabel.count(pii(i,j))) relabel[pii(i,j)] = ++cc;
            T.fd(relabel[pii(i,j)] , river.count(pii(i,j)));
            for(int k = 0 ; k < 4 ; k++){
                int u = i + dx[k] , v = j + dy[k];
                if(u >= 1 && v >= 1 && u <= R && v <= C && v <= j){
                    if(!relabel.count(pii(u,v))) relabel[pii(u,v)] = ++cc;
                    T.fd(relabel[pii(u,v)] , river.count(pii(u,v)));
                    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)));
                    }
                }
            }
        }
        tudo[j] = T.get_c();
    }
    T.clear_T();
    for(int j = 1 ; j <= C; j ++){
        int i = 1;
            if(!relabel.count(pii(i,j))) relabel[pii(i,j)] = ++cc;
            T.fd(relabel[pii(i,j)] , river.count(pii(i,j)));
            for(int k = 0 ; k < 4 ; k++){
                int u = i + dx[k] , v = j + dy[k];
                if(u >= 1 && v >= 1 && u <= 1 &&  v <=j ){
                    if(!relabel.count(pii(u,v))) relabel[pii(u,v)] = ++cc;
                    T.fd(relabel[pii(u,v)] , river.count(pii(u,v)));
                    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)));
                    }
                }
            }
        sum[i][j] = T.get_c();
    }    
    T.clear_T();
    for(int j = 1 ; j <= C; j ++){
        int i = 2;
            if(!relabel.count(pii(i,j))) relabel[pii(i,j)] = ++cc;
            T.fd(relabel[pii(i,j)] , river.count(pii(i,j)));
            for(int k = 0 ; k < 4 ; k++){
                int u = i + dx[k] , v = j + dy[k];
                if(u >= 1 && v >= 1 && u <= 2 && v <= j){
                    if(!relabel.count(pii(u,v))) relabel[pii(u,v)] = ++cc;
                    T.fd(relabel[pii(u,v)] , river.count(pii(u,v)));
                    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)));
                    }
                }
            }
        sum[i][j] = T.get_c();
    }
    RR = R , CC = C;
}

int colour(int ar, int ac, int br, int bc) {
    if(ar < br){
        int lff = 0;
        if(ac > 1) lff = tudo[ac-1];
        return tudo[bc] - lff;
    }
    else{
        return sum[ar][bc] - sum[ar][ac - 1];
    }
}
// #define int int

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:113:14: warning: array subscript is above array bounds [-Warray-bounds]
         sum[i][j] = T.get_c();
         ~~~~~^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26