Submission #254016

#	Time	Username	Problem	Language	Result	Execution time	Memory
254016		test2	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	512 KiB

apple

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7, mod = 1e9 + 7;

int n, m, q;
int ans[N];

struct mat
{

        int X = 0, Y = 0;

        vector<vector<long long>> rc;

        mat(int x, int y)
        {
                X = x;
                Y = y;
                for (int i = 0; i < x; i++)
                {
                        rc.push_back({});
                        rc[rc.size() - 1].resize(y);
                }
        }

        mat()
        {
        }

        mat(vector<vector<long long>> &bod)
        {
                rc = bod;
                X = bod.size();
                if (bod.size())
                        Y = bod[0].size();
        }

        mat mul(mat &rhs)
        {
                mat res = mat(X, rhs.Y);

                for (int i = 0; i < X; i++)
                {
                        for (int j = 0; j < rhs.Y; j++)
                        {
                                for (int k = 0; k < Y; k++)
                                {
                                        res.rc[i][j] += (1LL * rc[i][k] * rhs.rc[k][j]) % mod;
                                        res.rc[i][j] %= mod;
                                }
                        }
                }
                return res;
        }

        void print()
        {
                for (int i = 0; i < X; i++)
                {
                        for (int j = 0; j < Y; j++)
                        {
                                cout << rc[i][j] << " ";
                        }
                        cout << "\n";
                }
        }
};

mat mcores[32];

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);

        cin >> n >> m >> q;

        vector<vector<long long>> core;

        for (int i = 0; i < n; i++)
        {
                core.push_back({});
                for (int j = 0; j < n; j++)
                {
                        core.back().push_back(0);
                }
        }

        for (int i = 0; i < m; i++)
        {
                int u, v;
                cin >> u >> v;
                core[v - 1][u - 1]++;
        }

        vector<vector<long long>> iden;
        for (int i = 0; i < n; i++)
        {
                iden.push_back({{0}});
        }

        vector<vector<long long>> fin;

        for (int i = 0; i < n; i++)
        {
                fin.push_back({});
                for (int j = 0; j < n; j++)
                {
                        fin.back().push_back((i == j));
                }
        }

        mcores[0] = mat(core);

        for (int i = 1; i < 30; i++)
        {
                mcores[i] = mcores[i - 1].mul(mcores[i - 1]);
        }

        vector<pair<pair<int, int>, pair<int, int>>> qs;

        for (int i = 0; i < q; i++)
        {
                int a, b, k;
                cin >> a >> b >> k;
                qs.push_back({{k, i}, {a, b}});
        }
        sort(qs.begin(), qs.end());

        int l = 0;

        mat mcore = mat(core);
        mat mfin = mat(fin);

        for (auto u : qs)
        {
                int diff = u.first.first - l;
                
                for (int i = 0; i < 30; i++)
                {
                        if (diff & (1 << i))
                        {
                                mfin = mfin.mul(mcores[i]);
                        }
                }
                ans[u.first.second] = mfin.rc[u.second.second - 1][u.second.first - 1];
                l += diff;
        }
        for (int i = 0; i < q; i++)
        {
                cout << ans[i] << "\n";
        }

        return 0;
}

• Subtask 1: 0 / 100