Submission #984365

#	Time	Username	Problem	Language	Result	Execution time	Memory
984365		bachhoangxuan	Hexagonal Territory (APIO21_hexagon)	C++17	42 / 100	2090 ms	507532 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 1e9;
const int mod = 1e9+7;
const int inv2 = (mod+1)/2;
int dx[]={0,0,1,1,0,-1,-1},
    dy[]={0,1,1,0,-1,-1,0};

i32 draw_territory(i32 N, i32 A, i32 B,
                   std::vector<i32> D, std::vector<i32> L) {
    int X=0,Y=0;
    int a=0,b=0;
    for(int i=0;i<N;i++){
        b+=L[i];
        int nX=X+L[i]*dx[D[i]];
        int nY=Y+L[i]*dy[D[i]];
        a+=X*nY-Y*nX;
        X=nX;Y=nY;
    }
    a=(abs(a)+b)%mod;
    a=a*inv2%mod;
    a=(a+1)%mod;

    X=0,Y=0;
    vector<pii> p;
    set<pii> ss;
    for(int i=0;i<N;i++){
        for(int j=0;j<L[i];j++){
            X+=dx[D[i]];
            Y+=dy[D[i]];
            p.push_back({X,Y});
            for(int t=1;t<=6;t++) ss.insert({X+dx[t],Y+dy[t]});
        }
    }
    for(pii x:p) ss.erase(x);

    set<pii> outers;
    queue<pii> q;
    q.push(*ss.begin());
    outers.insert(*ss.begin());

    while(!q.empty()){
        auto [x,y]=q.front();q.pop();
        for(int t=1;t<=6;t++){
            pii cc={x+dx[t],y+dy[t]};
            if(ss.find(cc)!=ss.end() && outers.find(cc)==outers.end()){
                q.push(cc);
                outers.insert(cc);
            }
        }
    }

    map<int,vector<int>> mp;
    for(pii x:p){
        if(outers.find({x.fi,x.se-1})!=outers.end()) mp[x.fi].push_back(x.se);
        if(outers.find({x.fi,x.se+1})!=outers.end()) mp[x.fi].push_back(x.se);
    }

    int rt=-1,M=0,T=0;
    vector<int> cx;
    vector<pii> range;
    vector<vector<int>> edge;

    int px=-inf;
    vector<pii> pre;
    for(auto [x,v]:mp){
        sort(v.begin(),v.end());
        vector<pii> cc;
        for(int i=0;i<(int)v.size();i+=2){
            cc.push_back({v[i],v[i+1]});
            //cout << x << ' ' << v[i] << ' ' << v[i+1] << '\n';
        }
        if(px+1==x){
            int pos=0,S=M-(int)pre.size();
            for(auto p:cc){
                int l=p.fi,r=p.se;
                if(x==0 && l<=0 && 0<=r) rt=M;
                cx.push_back(x);
                edge.push_back({});
                range.push_back({l,r});

                while(pos<(int)pre.size() && pre[pos].se+1<l) pos++;
                int lst=pos;
                while(pos<(int)pre.size() && pre[pos].fi<=r){
                    edge[S+pos].push_back(M);
                    edge[M].push_back(S+pos);
                    lst=pos++;
                }
                pos=lst;M++;
            }
        }
        else{
            for(auto p:cc){
                if(x==0 && p.fi<=0 && 0<=p.se) rt=M;
                cx.push_back(x);
                edge.push_back({});
                range.push_back({p.fi,p.se});
                M++;
            }
        }
        px=x;pre=cc;
    }
    function<void(int,int,int,int,int)> dfs = [&](int u,int p,int l,int r,int d){
        auto [L,R]=range[u];
        //cout << u << ' ' << l << ' ' << r << ' ' << d << '\n';
        T=(T+(R-L+1)*d+(l-L)*(l-L+1)/2+(R-r)*(R-r+1)/2)%mod;
        for(int v:edge[u]){
            if(v==p) continue;
            auto [nL,nR]=range[v];
            int nl=l-(cx[v]<cx[u]),nr=r+(cx[v]>cx[u]);
            int cl=max(nl,nL),cr=min(nr,nR);
            if(cl<=cr) dfs(v,u,cl,cr,d+1);
            else if(nr<nL) dfs(v,u,nL,nL,d+nL-nr+1);
            else dfs(v,u,nR,nR,d+nl-nR+1);
        }
    };
    dfs(rt,-1,0,0,0);
    return (a*A+T*B)%mod;
}
#undef int

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 0 / 15
• Subtask 6: 19 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16