oj.uz

Submission #1025457

# Submission time Handle Problem Language Result Execution time Memory
1025457 2024-07-17T03:56:28 Z bachhoangxuan Hexagonal Territory (APIO21_hexagon) C++14
100 / 100
 240 ms 72480 KB 
#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 maxn = 2e5+5;
const int inv2 = (mod+1)/2;
const int inv3 = (mod+1)/3;
int dx[]={0,0,1,1,0,-1,-1},
    dy[]={0,1,1,0,-1,-1,0};

int S[maxn],T[maxn],p[maxn],d[maxn];
int f[maxn],mt[maxn],tp[maxn],lx[maxn],rx[maxn],ly[maxn],ry[maxn],cnt;
vector<int> h[maxn],com;
vector<pair<int,int>> g[maxn];
int dd[maxn],pos[maxn];

int get(int i,int x){
    return p[i]+x*d[i];
}
int X,Y;
bool cmp(int i,int j){
    int yi=get(i,X),yj=get(j,X);
    return (yi<yj) || (yi==yj && ((tp[i]==-1)==(tp[j]==-1) ? i!=j && (tp[i]==-1)^d[i]:i<j));
}
struct cmp_t{
    bool operator()(int i,const int j){
        return cmp(i,j);
    }
};
set<int,cmp_t> ss;
void add_edge(int u,int v){
    //cout << "edge " << u << ' ' << v << '\n';
    g[u].push_back(make_pair(v,X));
    g[v].push_back(make_pair(u,X));
}

void add(int l,int r){
    if(tp[l]==-1 && tp[r]==-1){
        auto it=ss.lower_bound(r);
        if(it==ss.end() || cmp(r,mt[*it])){
            tp[l]=0,tp[r]=1;
            mt[l]=r,mt[r]=l;
            lx[cnt]=X;
            ly[cnt]=l;
            ry[cnt]=r;
            f[l]=f[r]=cnt++;
            ss.insert(r);
        }
        else{
            int rt=*it,lt=mt[rt];
            tp[l]=1,tp[r]=0;
            ss.insert(l);
            add_edge(f[lt],cnt);
            add_edge(f[lt],cnt+1);
            rx[f[lt]]=lx[cnt]=lx[cnt+1]=X;
            mt[l]=lt,mt[lt]=l;
            mt[r]=rt,mt[rt]=r;
            ly[cnt]=lt,ry[cnt]=l;
            ly[cnt+1]=r,ry[cnt+1]=rt;
            f[l]=f[lt]=cnt++;
            f[r]=f[rt]=cnt++;
        }
    }
    else if(tp[l]==0 && tp[r]==1){
        ss.erase(r);
        tp[l]=tp[r]=-1;
        rx[f[l]]=X;
    }
    else if(tp[l]==1 && tp[r]==0){
        ss.erase(l);
        int lt=mt[l],rt=mt[r];
        tp[l]=tp[r]=-1;
        mt[lt]=rt,mt[rt]=lt;
        add_edge(f[l],cnt);
        add_edge(f[r],cnt);
        rx[f[l]]=rx[f[r]]=lx[cnt]=X;
        ly[cnt]=lt,ry[cnt]=rt;
        f[lt]=f[rt]=cnt++;
    }
    else{
        if(tp[r]==-1) swap(l,r);
        if(tp[r]==1){
            ss.erase(r);
            ss.insert(l);
        }
        int rt=mt[r];
        swap(tp[l],tp[r]);
        mt[l]=rt,mt[rt]=l;
        add_edge(f[r],cnt);
        rx[f[r]]=lx[cnt]=X;
        ly[cnt]=l,ry[cnt]=rt;
        if(tp[l]) swap(ly[cnt],ry[cnt]);
        f[l]=f[rt]=cnt++;
    }
}

int dfs(int u,int par){
    int res=0;
    int len=rx[u]-lx[u]+1,dl=get(ry[u],lx[u])-get(ly[u],lx[u])+1,dr=get(ry[u],rx[u])-get(ly[u],rx[u])+1;
    if(pos[u]==rx[u]) swap(dl,dr);
    res=((dl+dr)*len/2)%mod*dd[u]%mod;
    if(len>1){
        int k=(dr-dl)/(len-1);
        res=(res+len*(len-1)/2%mod*dl%mod)%mod;
        res=(res+len*(len-1)/2%mod*(2*len-1)%mod*inv3%mod*(mod+k)%mod)%mod;
    }
    //cout << u << ' ' << dd[u] << ' ' << dl << ' ' << dr << ' ' << len << '\n';
    //cout << res << '\n';

    for(auto [v,x]:g[u]){
        if(v==par) continue;
        pos[v]=x;dd[v]=dd[u]+abs(x-pos[u]);
        int l=max(get(ly[u],x),get(ly[v],x));
        int r=min(get(ry[u],x),get(ry[v],x));
        res=(res-(r-l+1)*dd[v]%mod+mod)%mod;
        //cout << "del " << (r-l+1)*dd[v]%mod << '\n';
        res=(res+dfs(v,u))%mod;
    }
    return res;
}

int solve(int N,vector<i32> D,vector<i32> L){
    for(int i=0;i<cnt;i++) g[i].clear();
    int n=0;cnt=X=Y=0;
    for(int i=0;i<N;i++){
        int nX=X+L[i]*dx[D[i]];
        int nY=Y+L[i]*dy[D[i]];
        if(X!=nX){
            S[n]=min(X,nX);
            T[n]=max(X,nX);
            d[n]=(nY-Y)/(nX-X);
            p[n]=Y-X*d[n];
            n++;
        }
        X=nX;Y=nY;
    }

    com.clear();
    for(int i=0;i<n;i++) com.push_back(S[i]),com.push_back(T[i]);
    sort(com.begin(),com.end());
    com.erase(unique(com.begin(),com.end()),com.end());
    int sz=(int)com.size();
    for(int i=0;i<sz;i++) h[i].clear();
    for(int i=0;i<n;i++){
        tp[i]=-1;
        h[lower_bound(com.begin(),com.end(),S[i])-com.begin()].push_back(i);
        h[lower_bound(com.begin(),com.end(),T[i])-com.begin()].push_back(i);
    }
    for(int i=0;i<sz;i++){
        X=com[i];
        sort(h[i].begin(),h[i].end(),cmp);
        for(int j=0;j<(int)h[i].size();j+=2) add(h[i][j],h[i][j+1]);
    }
    //for(int i=0;i<cnt;i++) cout << lx[i] << ' ' << rx[i] << ' ' << S[ly[i]] << ' ' << T[ly[i]] << ' ' << S[ry[i]] << ' ' << T[ry[i]] << '\n';

    int rt=-1;
    for(int i=0;i<cnt;i++) if(lx[i]<=0 && 0<=rx[i] && p[ly[i]]<=0 && p[ry[i]]>=0){rt=i;break;}
    dd[rt]=pos[rt]=0;
    return dfs(rt,-1);
}

i32 draw_territory(i32 N, i32 A, i32 B,
                   std::vector<i32> D, std::vector<i32> L) {
    int a=0,b=0;X=Y=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;

    B=B*inv2%mod;
    int T=0;
    for(int k=0;k<3;k++){
        T=(T+solve(N,D,L))%mod;
        for(int i=0;i<N;i++) D[i]=D[i]%6+1;
    }
    //cout << T << '\n';
    return (a*A+T*B)%mod;
}
#undef int

Compilation message

hexagon.cpp: In function 'long long int dfs(long long int, long long int)':
hexagon.cpp:116:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |     for(auto [v,x]:g[u]){
      |              ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Correct 4 ms 29112 KB Output is correct
4 Correct 4 ms 29016 KB Output is correct
5 Correct 4 ms 29020 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29140 KB Output is correct
2 Correct 4 ms 29016 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 4 ms 29020 KB Output is correct
6 Correct 3 ms 29020 KB Output is correct
7 Correct 4 ms 29016 KB Output is correct
8 Correct 4 ms 29016 KB Output is correct
9 Correct 5 ms 29020 KB Output is correct
10 Correct 4 ms 29144 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 4 ms 29020 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 4 ms 29392 KB Output is correct
5 Correct 4 ms 29016 KB Output is correct
6 Correct 4 ms 29140 KB Output is correct
7 Correct 3 ms 29020 KB Output is correct
8 Correct 4 ms 29140 KB Output is correct
9 Correct 4 ms 29020 KB Output is correct
10 Correct 3 ms 29140 KB Output is correct
11 Correct 3 ms 29020 KB Output is correct
12 Correct 4 ms 29140 KB Output is correct
13 Correct 4 ms 29020 KB Output is correct
14 Correct 4 ms 29020 KB Output is correct
15 Correct 4 ms 29020 KB Output is correct
16 Correct 4 ms 29020 KB Output is correct
17 Correct 4 ms 29020 KB Output is correct
18 Correct 4 ms 29140 KB Output is correct
19 Correct 4 ms 29020 KB Output is correct
20 Correct 3 ms 29132 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 12 ms 30132 KB Output is correct
3 Correct 6 ms 29276 KB Output is correct
4 Correct 5 ms 29276 KB Output is correct
5 Correct 8 ms 29788 KB Output is correct
6 Correct 13 ms 30300 KB Output is correct
7 Correct 35 ms 33484 KB Output is correct
8 Correct 4 ms 29272 KB Output is correct
9 Correct 4 ms 29276 KB Output is correct
10 Correct 4 ms 29020 KB Output is correct
11 Correct 39 ms 38416 KB Output is correct
12 Correct 39 ms 38208 KB Output is correct
13 Correct 38 ms 38332 KB Output is correct
14 Correct 47 ms 38172 KB Output is correct
15 Correct 5 ms 29272 KB Output is correct
16 Correct 5 ms 29272 KB Output is correct
17 Correct 4 ms 29144 KB Output is correct
18 Correct 4 ms 29020 KB Output is correct
19 Correct 5 ms 29016 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 5 ms 29136 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 10 ms 30008 KB Output is correct
5 Correct 5 ms 29276 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 8 ms 29788 KB Output is correct
8 Correct 12 ms 30300 KB Output is correct
9 Correct 31 ms 33480 KB Output is correct
10 Correct 5 ms 29272 KB Output is correct
11 Correct 4 ms 29276 KB Output is correct
12 Correct 5 ms 29020 KB Output is correct
13 Correct 37 ms 38324 KB Output is correct
14 Correct 38 ms 38204 KB Output is correct
15 Correct 35 ms 38400 KB Output is correct
16 Correct 50 ms 38448 KB Output is correct
17 Correct 5 ms 29276 KB Output is correct
18 Correct 4 ms 29276 KB Output is correct
19 Correct 4 ms 29020 KB Output is correct
20 Correct 75 ms 39000 KB Output is correct
21 Correct 12 ms 30300 KB Output is correct
22 Correct 7 ms 29636 KB Output is correct
23 Correct 118 ms 43128 KB Output is correct
24 Correct 184 ms 52400 KB Output is correct
25 Correct 192 ms 55368 KB Output is correct
26 Correct 101 ms 41964 KB Output is correct
27 Correct 76 ms 39628 KB Output is correct
28 Correct 50 ms 35452 KB Output is correct
29 Correct 178 ms 69500 KB Output is correct
30 Correct 165 ms 70548 KB Output is correct
31 Correct 154 ms 65964 KB Output is correct
32 Correct 198 ms 64664 KB Output is correct
33 Correct 98 ms 44004 KB Output is correct
34 Correct 46 ms 36956 KB Output is correct
35 Correct 4 ms 29020 KB Output is correct
36 Correct 6 ms 29020 KB Output is correct
37 Correct 5 ms 29128 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 3 ms 29140 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 4 ms 29140 KB Output is correct
5 Correct 5 ms 29016 KB Output is correct
6 Correct 4 ms 29020 KB Output is correct
7 Correct 4 ms 29108 KB Output is correct
8 Correct 4 ms 29020 KB Output is correct
9 Correct 3 ms 29020 KB Output is correct
10 Correct 4 ms 29016 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 4 ms 29020 KB Output is correct
13 Correct 4 ms 29020 KB Output is correct
14 Correct 4 ms 29020 KB Output is correct
15 Correct 5 ms 29020 KB Output is correct
16 Correct 4 ms 29136 KB Output is correct
17 Correct 4 ms 29160 KB Output is correct
18 Correct 4 ms 29020 KB Output is correct
19 Correct 13 ms 30004 KB Output is correct
20 Correct 7 ms 29276 KB Output is correct
21 Correct 4 ms 29276 KB Output is correct
22 Correct 9 ms 29784 KB Output is correct
23 Correct 12 ms 30300 KB Output is correct
24 Correct 33 ms 33448 KB Output is correct
25 Correct 5 ms 29276 KB Output is correct
26 Correct 5 ms 29276 KB Output is correct
27 Correct 5 ms 29020 KB Output is correct
28 Correct 52 ms 38344 KB Output is correct
29 Correct 41 ms 38208 KB Output is correct
30 Correct 37 ms 38236 KB Output is correct
31 Correct 48 ms 38072 KB Output is correct
32 Correct 5 ms 29276 KB Output is correct
33 Correct 4 ms 29156 KB Output is correct
34 Correct 4 ms 29016 KB Output is correct
35 Correct 14 ms 30300 KB Output is correct
36 Correct 6 ms 29276 KB Output is correct
37 Correct 5 ms 29276 KB Output is correct
38 Correct 12 ms 30296 KB Output is correct
39 Correct 12 ms 30556 KB Output is correct
40 Correct 32 ms 33488 KB Output is correct
41 Correct 4 ms 29272 KB Output is correct
42 Correct 5 ms 29276 KB Output is correct
43 Correct 4 ms 29020 KB Output is correct
44 Correct 52 ms 41716 KB Output is correct
45 Correct 57 ms 40564 KB Output is correct
46 Correct 55 ms 40396 KB Output is correct
47 Correct 49 ms 37164 KB Output is correct
48 Correct 5 ms 29276 KB Output is correct
49 Correct 5 ms 29272 KB Output is correct
50 Correct 4 ms 29020 KB Output is correct
51 Correct 5 ms 29168 KB Output is correct
52 Correct 5 ms 29020 KB Output is correct
53 Correct 4 ms 29020 KB Output is correct
54 Correct 4 ms 29020 KB Output is correct
55 Correct 4 ms 29020 KB Output is correct
56 Correct 4 ms 29020 KB Output is correct
57 Correct 4 ms 29020 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 4 ms 29108 KB Output is correct
4 Correct 4 ms 29116 KB Output is correct
5 Correct 4 ms 29016 KB Output is correct
6 Correct 95 ms 42408 KB Output is correct
7 Correct 94 ms 41796 KB Output is correct
8 Correct 92 ms 43488 KB Output is correct
9 Correct 7 ms 30040 KB Output is correct
10 Correct 14 ms 31200 KB Output is correct
11 Correct 16 ms 30940 KB Output is correct
12 Correct 222 ms 55960 KB Output is correct
13 Correct 198 ms 58520 KB Output is correct
14 Correct 188 ms 56884 KB Output is correct
15 Correct 130 ms 54756 KB Output is correct
16 Correct 124 ms 51736 KB Output is correct
17 Correct 134 ms 53876 KB Output is correct
18 Correct 240 ms 63092 KB Output is correct
19 Correct 160 ms 67444 KB Output is correct
20 Correct 123 ms 55776 KB Output is correct
21 Correct 4 ms 29016 KB Output is correct
22 Correct 4 ms 29172 KB Output is correct
23 Correct 4 ms 29016 KB Output is correct
24 Correct 4 ms 29020 KB Output is correct
25 Correct 4 ms 29016 KB Output is correct
26 Correct 4 ms 29020 KB Output is correct
27 Correct 4 ms 29112 KB Output is correct
28 Correct 4 ms 29020 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29016 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 4 ms 29144 KB Output is correct
5 Correct 4 ms 29020 KB Output is correct
6 Correct 3 ms 29020 KB Output is correct
7 Correct 4 ms 29016 KB Output is correct
8 Correct 4 ms 29140 KB Output is correct
9 Correct 4 ms 29020 KB Output is correct
10 Correct 4 ms 29020 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 4 ms 29136 KB Output is correct
13 Correct 3 ms 29144 KB Output is correct
14 Correct 4 ms 29020 KB Output is correct
15 Correct 4 ms 29020 KB Output is correct
16 Correct 4 ms 29140 KB Output is correct
17 Correct 4 ms 29020 KB Output is correct
18 Correct 4 ms 29020 KB Output is correct
19 Correct 3 ms 29020 KB Output is correct
20 Correct 4 ms 29020 KB Output is correct
21 Correct 4 ms 29144 KB Output is correct
22 Correct 4 ms 29020 KB Output is correct
23 Correct 12 ms 30044 KB Output is correct
24 Correct 5 ms 29276 KB Output is correct
25 Correct 4 ms 29128 KB Output is correct
26 Correct 8 ms 29804 KB Output is correct
27 Correct 12 ms 30272 KB Output is correct
28 Correct 34 ms 33480 KB Output is correct
29 Correct 6 ms 29276 KB Output is correct
30 Correct 5 ms 29276 KB Output is correct
31 Correct 5 ms 29020 KB Output is correct
32 Correct 40 ms 38352 KB Output is correct
33 Correct 38 ms 38204 KB Output is correct
34 Correct 37 ms 38328 KB Output is correct
35 Correct 49 ms 38188 KB Output is correct
36 Correct 6 ms 29272 KB Output is correct
37 Correct 4 ms 29020 KB Output is correct
38 Correct 4 ms 29020 KB Output is correct
39 Correct 75 ms 39000 KB Output is correct
40 Correct 17 ms 30300 KB Output is correct
41 Correct 10 ms 29532 KB Output is correct
42 Correct 111 ms 43308 KB Output is correct
43 Correct 192 ms 52552 KB Output is correct
44 Correct 178 ms 55332 KB Output is correct
45 Correct 126 ms 42144 KB Output is correct
46 Correct 75 ms 39380 KB Output is correct
47 Correct 51 ms 35448 KB Output is correct
48 Correct 178 ms 69820 KB Output is correct
49 Correct 182 ms 70480 KB Output is correct
50 Correct 164 ms 65464 KB Output is correct
51 Correct 218 ms 64404 KB Output is correct
52 Correct 100 ms 44000 KB Output is correct
53 Correct 47 ms 36948 KB Output is correct
54 Correct 4 ms 29016 KB Output is correct
55 Correct 12 ms 30216 KB Output is correct
56 Correct 5 ms 29276 KB Output is correct
57 Correct 5 ms 29276 KB Output is correct
58 Correct 13 ms 30272 KB Output is correct
59 Correct 13 ms 30556 KB Output is correct
60 Correct 38 ms 33484 KB Output is correct
61 Correct 5 ms 29276 KB Output is correct
62 Correct 5 ms 29276 KB Output is correct
63 Correct 4 ms 29020 KB Output is correct
64 Correct 54 ms 41780 KB Output is correct
65 Correct 54 ms 40424 KB Output is correct
66 Correct 57 ms 40396 KB Output is correct
67 Correct 49 ms 37416 KB Output is correct
68 Correct 5 ms 29272 KB Output is correct
69 Correct 4 ms 29156 KB Output is correct
70 Correct 4 ms 29020 KB Output is correct
71 Correct 112 ms 42488 KB Output is correct
72 Correct 87 ms 41776 KB Output is correct
73 Correct 88 ms 43492 KB Output is correct
74 Correct 7 ms 29788 KB Output is correct
75 Correct 14 ms 31076 KB Output is correct
76 Correct 14 ms 30940 KB Output is correct
77 Correct 180 ms 57752 KB Output is correct
78 Correct 195 ms 58776 KB Output is correct
79 Correct 187 ms 57272 KB Output is correct
80 Correct 127 ms 54832 KB Output is correct
81 Correct 127 ms 51736 KB Output is correct
82 Correct 131 ms 53996 KB Output is correct
83 Correct 172 ms 62956 KB Output is correct
84 Correct 156 ms 67440 KB Output is correct
85 Correct 118 ms 55896 KB Output is correct
86 Correct 4 ms 29016 KB Output is correct
87 Correct 79 ms 37852 KB Output is correct
88 Correct 13 ms 30556 KB Output is correct
89 Correct 6 ms 29532 KB Output is correct
90 Correct 100 ms 43108 KB Output is correct
91 Correct 170 ms 53604 KB Output is correct
92 Correct 206 ms 56872 KB Output is correct
93 Correct 105 ms 43780 KB Output is correct
94 Correct 69 ms 38868 KB Output is correct
95 Correct 48 ms 35672 KB Output is correct
96 Correct 154 ms 66236 KB Output is correct
97 Correct 166 ms 72480 KB Output is correct
98 Correct 157 ms 68004 KB Output is correct
99 Correct 188 ms 60200 KB Output is correct
100 Correct 85 ms 43744 KB Output is correct
101 Correct 43 ms 36688 KB Output is correct
102 Correct 3 ms 29020 KB Output is correct
103 Correct 3 ms 29020 KB Output is correct
104 Correct 3 ms 29020 KB Output is correct
105 Correct 3 ms 29020 KB Output is correct
106 Correct 4 ms 29016 KB Output is correct
107 Correct 3 ms 29020 KB Output is correct
108 Correct 3 ms 29020 KB Output is correct
109 Correct 3 ms 29020 KB Output is correct