제출 #707264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707264		Nhoksocqt1	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	69 / 100	5063 ms	61524 KiB

garden

#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 150005;

struct Edge {
    int u, v;
} edge[MAXN];

vector<ii> adj[MAXN];
vector<int> adjp[2 * MAXN], comp[2 * MAXN], B[2 * MAXN];
ii a[2 * MAXN], b[2 * MAXN], itOf[2 * MAXN];
int h[2 * MAXN], timeIn[2 * MAXN], timeOut[2 * MAXN], result[2005];
int firstToLoop[2 * MAXN], firstInLoop[2 * MAXN], loopOf[2 * MAXN], posInComp[2 * MAXN];
int deg[2 * MAXN], pa[2 * MAXN], idc[2 * MAXN], idn[2 * MAXN], numNode, numEdge, numQuery, lastNode;
bool dx[2 * MAXN], ok[2 * MAXN];

inline int getLeftNode(int id) {
    return (id >= numEdge) ? edge[id - numEdge].v : edge[id].u;
}

int timeIn0;
void preDfs(int u, int p) {
    timeIn[u] = ++timeIn0;
    if(ok[u])
        B[h[u]].push_back(timeIn[u]);

    for (int it = 0; it < int(adjp[u].size()); ++it) {
        int v(adjp[u][it]);
        if(v != p) {
            h[v] = 1 + h[u];
            preDfs(v, u);
        }
    }

    timeOut[u] = timeIn0;
}

void count_routes(int _N, int _M, int _P, int _R[][2], int _Q, int _G[]) {
    numNode = _N, numEdge = _M, lastNode = _P, numQuery = _Q;
    for (int i = 0; i < _M; ++i) {
        int u(_R[i][0]), v(_R[i][1]);
        edge[i] = {u, v};
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    for (int u = 0; u < numNode; ++u) {
        int id0 = adj[u][0].se;
        int id1 = (adj[u].size() > 1 ? adj[u][1].se : 1e9+7);
        bool type0 = (u == edge[adj[u][0].se].v);
        bool type1 = (adj[u].size() > 1 && (u == edge[adj[u][1].se].v));

        for (int it = 0; it < int(adj[u].size()); ++it) {
            int v(adj[u][it].fi), id(adj[u][it].se);
            bool type = !(u == edge[id].v);
            if(it == 0) {
                idn[u] = id + !type * numEdge;
                ok[idn[u]] = 1;
            }

            pa[id + type * numEdge] = (id != id0 || id1 >= 1e9+7) ? id0 + type0 * numEdge : id1 + type1 * numEdge;
            ++deg[pa[id + type * numEdge]];
        }
    }

    int numComp(0);
    for (int id = 0; id < 2 * numEdge; ++id) {
        if(deg[id] || dx[id])
            continue;

        vector<int> tmpn;
        int tmp(id);
        while(!dx[tmp]) {
            dx[tmp] = 1;
            tmpn.push_back(tmp);
            tmp = pa[tmp];
        }

        int szn(tmpn.size());
        for (int it = 0; it <= szn; ++it) {
            if(it == szn || tmpn[it] == tmp) {
                if(it < szn) {
                    for (int jt = it; jt < szn; ++jt) {
                        posInComp[tmpn[jt]] = jt - it;
                        comp[numComp].push_back(tmpn[jt]);
                        firstInLoop[tmpn[jt]] = tmpn[jt];
                        loopOf[tmpn[jt]] = szn - it;
                        firstToLoop[tmpn[jt]] = 0;
                        idc[tmpn[jt]] = numComp;
                    }

                    ++numComp;
                }

                if(it > 0) {
                    adjp[tmp].push_back(tmpn[it - 1]);
                    for (int jt = 0; jt < it; ++jt) {
                        posInComp[tmpn[jt]] = jt;
                        comp[numComp].push_back(tmpn[jt]);
                        firstToLoop[tmpn[jt]] = it - jt + firstToLoop[tmp];
                        firstInLoop[tmpn[jt]] = firstInLoop[tmp];
                        idc[tmpn[jt]] = numComp;
                        if(jt + 1 < it)
                            adjp[tmpn[jt + 1]].push_back(tmpn[jt]);
                    }

                    ++numComp;
                }

                break;
            }
        }
    }

    for (int id = 0; id < 2 * numEdge; ++id) {
        if(!deg[id] || dx[id])
            continue;

        int tmp(id);
        while(!dx[tmp]) {
            dx[tmp] = 1;
            posInComp[tmp] = comp[numComp].size();
            comp[numComp].push_back(tmp);
            idc[tmp] = numComp;
            firstToLoop[tmp] = 0;
            firstInLoop[tmp] = tmp;
            tmp = pa[tmp];
        }

        int szn(comp[numComp].size());
        for (int it = 0; it < szn; ++it)
            loopOf[comp[numComp][it]] = szn;

        ++numComp;
    }

    for (int id = 0; id < 2 * numEdge; ++id) {
        if(!timeIn[id])
            preDfs(id, -1);

        /*cout << id << ": ";
        for (int it = 0; it < int(adjp[id].size()); ++it)
            cout << adjp[id][it] << ' ';
        cout << '\n';*/
        //cout << id << ' ' << firstToLoop[id] << '\n';
        a[id] = {timeIn[id], id};
        b[id] = {timeOut[id], id};
    }

    sort(a, a + 2 * numEdge);
    sort(b, b + 2 * numEdge);

    for (int itn = 0; itn < 2 * numEdge; ++itn) {
        int id(a[itn].se);
        if(adjp[id].size() == 0 || getLeftNode(id) != lastNode)
            continue;

        for (int t = 0; t < numQuery; ++t) {
            int K(_G[t]);
            if(h[id] + K > 2 * numEdge)
                continue;

            h[id] += K;
            int szB(B[h[id]].size());
            while(itOf[h[id]].fi < szB && B[h[id]][itOf[h[id]].fi] <= timeOut[id])
                ++itOf[h[id]].fi;

            result[t] += itOf[h[id]].fi;
            //cout << t << ' ' << id << ' ' << itOf[h[id]].fi << '\n';
            h[id] -= K;
        }
    }

    for (int itn = 0; itn < 2 * numEdge; ++itn) {
        int id(b[itn].se);
        if(adjp[id].size() == 0 || getLeftNode(id) != lastNode)
            continue;

        for (int t = 0; t < numQuery; ++t) {
            int K(_G[t]);
            if(h[id] + K > 2 * numEdge)
                continue;

            h[id] += K;
            int szB(B[h[id]].size());
            while(itOf[h[id]].se < szB && B[h[id]][itOf[h[id]].se] < timeIn[id])
                ++itOf[h[id]].se;

            result[t] -= itOf[h[id]].se;
            //cout << t << ' ' << id << ' ' << itOf[h[id]].se << '\n';
            h[id] -= K;
        }
    }

    for (int t = 0; t < numQuery; ++t) {
        int K(_G[t]), cnt(result[t]);
        for (int u = 0; u < numNode; ++u) {
            if(firstToLoop[idn[u]] >= K)
                continue;

            int id(firstInLoop[idn[u]]), posn = (posInComp[id] + K - firstToLoop[idn[u]]) % loopOf[id];
            cnt += (getLeftNode(comp[idc[id]][posn]) == lastNode);
        }

        answer(cnt);
        //cout << cnt << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("O3")
      | 
garden.cpp:9: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("unroll-loops")
      | 
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:77:17: warning: unused variable 'v' [-Wunused-variable]
   77 |             int v(adj[u][it].fi), id(adj[u][it].se);
      |                 ^

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31