oj.uz

답안 #753939

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753939 2023-06-06T11:05:05 Z lukameladze 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
49 / 100
 103 ms 100888 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int MX = 3e5 + 5;
int n,m,q,p,k[MX],dist[MX],ans[MX], in_cycle, cycle_l,best[MX], s_best[MX],ans1[MX];
vector <int> v[MX], vr[MX],n_g[MX];
vector <pii> g[MX];
int can(int i) {
    return 2 * i - 1;
}
int cnnt(int i) {
    return 2 * i;
}
 
void bfs(int a) {
    queue <int> q;
    int pp = a;
    for (int i = 1; i <= 2 * n; i++) {
        dist[i] = -1;
    }
    q.push(a); dist[a] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int to : vr[x]) {
            if (to == pp) {
                in_cycle = 1;
                cycle_l = dist[x] + 1;
            }
            if (dist[to] == -1) {
                dist[to] = dist[x] + 1;
                q.push(to);
            }
        }
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n = N; m = M; p = P; p++; q = Q;
	for (int i = 1; i <= m; i++) {
		int a, b;
		a = R[i - 1][0]; b = R[i - 1][1];
		a++; b++;
		g[a].pb({i - 1, b});
		g[b].pb({i - 1, a});
	}
    for (int i = 1; i <= q; i++) {
        k[i] = G[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
        best[i] = g[i][0].s;
        s_best[i] = ((int)g[i].size() == 1 ? g[i][0].s : g[i][1].s);
    }
    for (int i = 1; i <= n; i++) {
        int a = i, b = best[i];
        if (best[b] == a) n_g[can(a)].pb(cnnt(b));
        else n_g[can(a)].pb(can(b));
 
        b = s_best[i];
        if (best[b] == a) n_g[cnnt(a)].pb(cnnt(b));
        else n_g[cnnt(a)].pb(can(b));
    }
    for (int i = 1; i <= n; i++) {
        v[i].clear();
    }
    for (int i = 1; i <= 2 * n; i++) {
        for (int x : n_g[i]) {
//            cout<<i<<" -- "<<x<<"\n";
            v[i].pb(x); vr[x].pb(i);
        }
    }
    bfs(can(p));
    for (int i = 1; i <= n; i++) {
        if (dist[can(i)] == -1) continue;
        ans[dist[can(i)]]++;
    }
    int fin = in_cycle, fl = cycle_l;
/*    if (in_cycle) {
        for (int i = cycle_l; i < MX; i++) {
            ans[i] += ans[i - cycle_l];
        }
    }*/
    in_cycle = 0;
    bfs(cnnt(p));
    int c_in = in_cycle, sl = cycle_l;
    for (int i = 1; i <= n; i++) {
        if (dist[can(i)] == -1) continue;
        ans1[dist[can(i)]]++;
    }
/*    if(in_cycle) {
        for (int i = cycle_l; i < MX; i++) {
            ans1[i] += ans1[i - cycle_l];
        }
    }*/
	for(int i = 1; i <= q; i++) {
		int res = 0;
		int x = k[i] % fl, y = k[i] % sl;
		res += ans[k[i]]; res += ans1[k[i]];
		if (fin) {
			for (int j = x; j <= min(k[i], n); j += fl) {
				if (j == k[i]) continue;
				res += ans[j];
			}	
		}
		if (c_in) {
			for (int j = y; j <= min(k[i], n); j += sl) {
				if (j == k[i]) continue;
				res += ans1[j];
			}
		}	
		answer(res);
	}
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28628 KB Output is correct
2 Correct 16 ms 28768 KB Output is correct
3 Correct 13 ms 28760 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 15 ms 28544 KB Output is correct
6 Correct 15 ms 28756 KB Output is correct
7 Correct 14 ms 28472 KB Output is correct
8 Correct 14 ms 28720 KB Output is correct
9 Correct 16 ms 28884 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28628 KB Output is correct
2 Correct 16 ms 28768 KB Output is correct
3 Correct 13 ms 28760 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 15 ms 28544 KB Output is correct
6 Correct 15 ms 28756 KB Output is correct
7 Correct 14 ms 28472 KB Output is correct
8 Correct 14 ms 28720 KB Output is correct
9 Correct 16 ms 28884 KB Output is correct
10 Correct 16 ms 28564 KB Output is correct
11 Correct 27 ms 33620 KB Output is correct
12 Correct 53 ms 37224 KB Output is correct
13 Runtime error 103 ms 100888 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28628 KB Output is correct
2 Correct 16 ms 28768 KB Output is correct
3 Correct 13 ms 28760 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 15 ms 28544 KB Output is correct
6 Correct 15 ms 28756 KB Output is correct
7 Correct 14 ms 28472 KB Output is correct
8 Correct 14 ms 28720 KB Output is correct
9 Correct 16 ms 28884 KB Output is correct
10 Correct 16 ms 28564 KB Output is correct
11 Correct 27 ms 33620 KB Output is correct
12 Correct 53 ms 37224 KB Output is correct
13 Runtime error 103 ms 100888 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -