Submission #403039

#	Time	Username	Problem	Language	Result	Execution time	Memory
403039		teehandsome	Land of the Rainbow Gold (APIO17_rainbow)	C++11	0 / 100	132 ms	55492 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxn=2e6;
int dm[4]={-1,0,1,0};
int dn[4]={0,1,0,-1};
char dir[4]={'N','E','S','W'};
vector<int> adj[mxn];
set<pii> pos;
int flag[mxn];
int ans;

void dfs(int u,int p) {
    if(flag[u]==2) return;
    if(flag[u]==1) {
        ans++; return;
    }
    else {
        flag[u]=1;
        for(auto v:adj[u]) {
            if(v==p) continue;
            dfs(v,u);
        }
        flag[u]=2;
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    pos.insert({sr,sc});
    for(int i=0;i<M;i++) {
        for(int j=0;j<4;j++) {
            if(dir[j]==S[i]) {
                sr+=dm[j]; sc+=dn[j]; break;
            }
        }
        pos.insert({sr,sc});
    }
}


int colour(int ar, int ac, int br, int bc) {
    for(int j=ac-1;j<=bc+1;j++) {
        pos.insert({ar-1,j});
        pos.insert({br+1,j});
    }
    for(int i=ar-1;i<=br+1;i++) {
        pos.insert({i,ac-1});
        pos.insert({i,bc+1});
    }
    vector<pii> a(all(pos));
    int len=a.size();
    for(int i=0;i<len;i++) {
        for(int j=0;j<4;j++) {
            int mm=a[i].first+dm[j];
            int nn=a[i].second+dn[j];
            int p=lower_bound(all(a),make_pair(mm,nn))-begin(a);
            if(p<len and a[p]==make_pair(mm,nn)) {
                adj[i].push_back(p);
            }
        }
    }
    for(int i=0;i<len;i++) {
        if(flag[i]==0) {
            dfs(i,i);
        }
    }
    return ans;
}

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