제출 #559021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559021		ngpin04	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	69 / 100	5050 ms	38608 KiB

garden

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
const int Nmax = 3e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

#include "garden.h"
#include "gardenlib.h"
//#include "grader.cpp"

vector <int> adj[Nmax];
vector <int> vt[Nmax];
vector <int> s;

pair <int, int> ed[Nmax];
pair <int, int> mn[Nmax];

int anc[Nmax][20];
int ptr[Nmax];
int h[Nmax];
int n,m,p,q,cnt;

bool flag[Nmax];
bool vis[Nmax];
bool ins[Nmax];
bool cyc[Nmax];
bool ok[Nmax];

void dfs(int i) {
    if (ins[i]) {
        cnt++;
        int j;
        do {
            j = s.back();
            s.pop_back();
            cyc[j] = true;
            ins[j] = false;
            vt[cnt].push_back(j);
        } while (j != i);
        reverse(ALL(vt[cnt]));
        return;
    }
    if (vis[i])
        return;

    vis[i] = true;
    ins[i] = true;
    s.push_back(i);
    dfs(ptr[i]);

    if (ins[i]) {
        ins[i] = false;
        s.pop_back();
    }
}

void build() {
    m <<= 1;
    for (int i = 0; i < n; i++)
        mn[i] = mp(oo, oo);

    for (int i = 0; i < m; i++) {
        int u = ed[i].fi;
        int v = ed[i].se;
        mini(mn[u].se, i);
        if (mn[u].se < mn[u].fi)
            swap(mn[u].fi, mn[u].se);
    }

    for (int i = 0; i < m; i++) {
        int u = ed[i].fi;
        int v = ed[i].se;
        if (mn[v].fi == (i ^ 1)) {
            if (mn[v].se == oo)
                ptr[i] = (i ^ 1);
            else
                ptr[i] = mn[v].se; 
        } else {
            ptr[i] = mn[v].fi;
        }
    }

    for (int i = 0; i < m; i++) if (!vis[i]) {
        s.clear();
        dfs(i);
    }

    for (int i = 0; i < m; i++) 
        adj[ptr[i]].push_back(i);

    for (int i = 0; i < n; i++)
        flag[mn[i].fi] = true;
}

void solve(int u, vector <int> &vt, int cur, int k) {
    if (cur < 0)
        cur = (int) vt.size() - 1;
    s.push_back(u);

    int sz = s.size();
    if (flag[u]) {
        if (sz > k) {
            int v = s[sz - k - 1];
            if (ed[v].se == p)
                ok[u] = true;
        } else {
            int v = vt[cur];
            if (ed[v].se == p)
                ok[u] = true;
        }
    }

    for (int v : adj[u]) 
        if (!cyc[v]) 
            solve(v, vt, cur - 1, k);

    s.pop_back();
}

int solve(int k) {
    for (int i = 0; i < m; i++)
        ok[i] = false;

    k--;
    for (int i = 1; i <= cnt; i++) 
    for (int j = 0, cur = k % (int) vt[i].size(); j < (int) vt[i].size(); j++) {
        solve(vt[i][j], vt[i], cur, k);
        cur++;
        if (cur == (int) vt[i].size())
            cur = 0;
    }

    int res = 0;
    for (int i = 0; i < n; i++)
        res += ok[mn[i].fi];

    return res;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    for (int i = 0; i < M; i++)
    for (int j = 0; j < 2; j++)
        ed[i << 1 | j] = mp(R[i][j], R[i][j ^ 1]);

    n = N;
    m = M;
    p = P;
    q = Q;

    build();
    if (N * Q >= 1e8)
        return;
    for (int i = 0; i < q; i++) 
        answer(solve(G[i]));
}   

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

garden.cpp: In function 'void build()':
garden.cpp:77:13: warning: unused variable 'v' [-Wunused-variable]
   77 |         int v = ed[i].se;
      |             ^
garden.cpp:84:13: warning: unused variable 'u' [-Wunused-variable]
   84 |         int u = ed[i].fi;
      |             ^

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