Submission #1078916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078916		dwuy	Tropical Garden (IOI11_garden)	C++14	100 / 100	1097 ms	32832 KiB

garden

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 5e8;
const int MX = 350005;

int n, m, P;
int L1, L2;
int deg[MX];
int nxt[MX];
int dis1[MX];
int dis2[MX];
vector<int> rG[MX];

void dfs1(int u){
    for(int v: rG[u]) if(dis1[v] > dis1[u] + 1){
        dis1[v] = dis1[u] + 1;
        dfs1(v);
    }
}

void dfs2(int u){
    for(int v: rG[u]) if(dis2[v] > dis2[u] + 1){
        dis2[v] = dis2[u] + 1;
        dfs2(v);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int QR[]){
    n = N;
    m = M;
    ::P = ++P;
    memset(nxt, -1, sizeof nxt);
    for(int i=0; i<m; i++) deg[R[i][0] + 1]++, deg[R[i][1] + 1]++;
    for(int i=0; i<m; i++){
        int u = R[i][0] + 1;
        int v = R[i][1] + 1;
        if(nxt[u] == -1) nxt[u] = deg[v] > 1 && nxt[v] == -1? v + n : v;
        else if(nxt[u + n] == -1) nxt[u + n] = deg[v] > 1 && nxt[v] == -1? v + n : v;
        if(nxt[v] == -1) nxt[v] = deg[u] > 1 && nxt[u] == v + n? u + n : u;
        else if(nxt[v + n] == -1) nxt[v + n] = deg[u] > 1 && nxt[u] == v? u + n : u;
    }
    for(int i=1; i<=n+n; i++) rG[nxt[i]].push_back(i);
    memset(dis1, 0x3f, sizeof dis1);
    memset(dis2, 0x3f, sizeof dis2);
    dis1[P] = dis2[P + n] = 0;
    dfs1(P);
    dfs2(P + n);

    int L1 = INF;
    int L2 = INF;
    for(int u=P, i=1; i<=n+n; i++){
        u = nxt[u];
        if(u == P){
            L1 = i;
            break;
        }
    }
    for(int u=P+n, i=1; i<=n+n; i++){
        u = nxt[u];
        if(u == P + n){
            L2 = i;
            break;
        }
    }
    for(int i=0; i<Q; i++){
        int k = QR[i];
        int ans = 0;
        for(int i=1; i<=n; i++){
            if(k >= dis1[i] && (k - dis1[i])%L1 == 0) ans++;
            else if(k >= dis2[i] && (k - dis2[i])%L2 == 0) ans++;
        }
        answer(ans);
    }
}

/*
6 8 0
1 3
0 2
3 5
0 4
4 3
2 5
4 1
2 3
10
1 8 192 384 3476 9483 23417 332764 342 46  




*/

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