Submission #439862

# Submission time Handle Problem Language Result Execution time Memory
439862 2021-07-01T03:33:37 Z 반딧불(#7618) Hexagonal Territory (APIO21_hexagon) C++17
3 / 100
1 ms 288 KB
#include <bits/stdc++.h>
#include "hexagon.h"

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;
const ll INV2 = 500000004;
const ll INV3 = 333333336;
const int xx[]={0, 1, 1, 0, -1, -1}, yy[]={2, 1, -1, -2, -1, 1};
ll A, B;

namespace basicMath{ /// �⺻���� ����� ����ϴ� �Լ����� ���� �̸������̴�.
    ll sum_1b (ll b){ /// 0���� b������ ������ ���� ��ȯ�Ѵ�.
        return (b * (b+1) % MOD * INV2 % MOD);
    }

    ll sum_ab (ll a, ll b){ /// a���� b������ ������ ���� ��ȯ�Ѵ�.
        return (sum_1b(b) - sum_1b(a-1) + MOD) % MOD;
    }

    ll sum_1b2 (ll b){ /// 0���� b������ ������ ������ ���� ��ȯ�Ѵ�.
        return (b * (b+1) % MOD * (b+b+1) % MOD * INV2 % MOD * INV3 % MOD);
    }

    ll sum_ab2 (ll a, ll b){ /// a���� b������ ������ ������ ���� ��ȯ�Ѵ�.
        return (sum_1b2(b) - sum_1b2(a-1) + MOD) % MOD;
    }

    ll sum_mult(ll s, ll e, ll d, ll l){
        /// �Ա��� �β��� s, �ⱸ�� �β��� e�̴�.
        /// �Ա��� �ⱸ ������ �Ÿ��� l�̰�, �������� �Ա� ������ �Ÿ��� d�̴�.
        ll numberOfPoints = 0; /// ���� ������, ���⿡ A�� ���ؾ� �Ѵ�.
        ll distanceSum = 0; /// �Ÿ� ������, ���⿡ B�� ���ؾ� �Ѵ�.
        if(s < e){ /// �β��� ���� Ŀ���� ��츦 ����Ѵ�.
            numberOfPoints = sum_ab(s+1, e-1);
            distanceSum = (sum_ab2(s+1, e-1) + (d-s)*sum_ab(s+1, e-1)%MOD + MOD) % MOD;
        }
        else if(s == e){ /// �β��� ������ ��츦 ����Ѵ�.
            numberOfPoints = (l-1) * s % MOD;
            distanceSum = sum_ab(d+1, d+l-1);
        }
        else{
            numberOfPoints = sum_ab(e+1, s-1);
            distanceSum = (s*s%MOD*(s-e-1)%MOD - sum_1b2(s-e+1)%MOD + (d-s)*sum_ab(e+1, s-1)%MOD + MOD + MOD) % MOD;
        }
        return (A * numberOfPoints + B * distanceSum) % MOD;
    }
}
using namespace basicMath;

namespace Calculator{
    struct Node { /// Ʈ���� ��� ����ü�� �����Ѵ�.
        ll weight; /// ����� ����ġ (�ش� ���� ���� �����ϴ� �� ����)�� �����Ѵ�.
        struct Edge{ /// Ʈ���� ���� ����ü�� �����Ѵ�.
            Node* cur; /// ���� ������ �ǹ��ϴ� ��� ������ �����̴�.
            Node* nxt; /// ��ǥ ������ �ǹ��ϴ� ��� ������ �����̴�.
            ll slope;  /// ������ �β� ��ȭ�� �ǹ��ϴ� �����̴�.
            ll len;    /// ������ ���̸� �ǹ��ϴ� �����̴�.

            Edge(Node* cur, Node* nxt, ll slope, ll len): cur(cur), nxt(nxt), slope(slope), len(len){} /// ������ �������̴�.
        };
        vector<Edge> link; /// Ʈ�� ����� ���� ����Ʈ�̴�.

        Node(ll weight): weight(weight){} /// ����� �������̴�.

        ll calculateAnswer(Node* prv = nullptr, ll dist = 0){ /// Ʈ�� ������ dfs�� ���� ���� ����ϴ� �Լ��̴�.
            ll returnValue = (A * weight + B * dist % MOD * weight) % MOD;
            for(Edge edge: link){ /// ���� �������� ��ȸ�Ѵ�.
                if(edge.nxt == prv) continue; /// �̹� �湮�� ������ �湮���� �ʴ´�.
                if(edge.len >= 2){
                    returnValue += sum_mult(weight, edge.nxt->weight, dist, edge.len); /// ���� ������ ���� �����Ѵ�.
                    returnValue %= MOD;
                }
                returnValue += edge.nxt->calculateAnswer(this, dist + edge.len); /// ���� �������� �̵��Ѵ�.
                returnValue %= MOD;
            }
            return returnValue; /// ���� ��ȯ�Ѵ�.
        }
    };

    vector<Node*> makeTree(int N, vector<int> D, vector<int> L){ /// Ʈ���� �����ϴ� �Լ��̴�.
        Node* node1 = new Node(1);
        Node* node2 = new Node(L[0]+1);
        node1->link.push_back(Node::Edge(node1, node2, 1, L[0]));
        node2->link.push_back(Node::Edge(node2, node1, -1, L[0]));
        return vector<Node*> {node1, node2};
    }

    ll calc(int N, vector<int> D, vector<int> L){
        /// Ǯ�̴� ũ�� �� �ܰ�� ���� �� �ִ�.
        /// ù ��° �ܰ�: Ʈ���� �����ϱ�
        /// �� ��° �ܰ�: Ʈ�� ������ Ʈ�� DP�� �����ؼ� ������ ���

        vector<Node*> nodeList = makeTree(N, D, L);      /// Ʈ���� �����Ѵ�.
        ll returnValue = nodeList[0]->calculateAnswer(); /// Ʈ�� ������ ���� ����Ѵ�.

        for(Node* pnt: nodeList){ /// ����� �޸𸮸� ������ �ش�.
            delete pnt;
        }
        return returnValue; /// ���� ��ȯ�Ѵ�.
    }
}

int draw_territory(int N, int _A, int _B, vector<int> D, vector<int> L){
    A = _A * 2 * INV3 % MOD, B = _B;
    for(int i=0; i<N; i++) D[i]--;
    ll Answer = 0;
    Answer += Calculator::calc(N, D, L);
    for(int i=0; i<N; i++) D[i] = (D[i] + 1) % 6;
    Answer += Calculator::calc(N, D, L);
    for(int i=0; i<N; i++) D[i] = (D[i] + 1) % 6;
    Answer += Calculator::calc(N, D, L);
    Answer %= MOD;
    Answer *= INV2;
    Answer %= MOD;
    return Answer;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 276 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -