oj.uz

Submission #1078373

# Submission time Handle Problem Language Result Execution time Memory
1078373 2024-08-27T15:58:43 Z dwuy Tropical Garden (IOI11_garden) C++14
49 / 100
 33 ms 14432 KB 
/**         - 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 = 150005;

int n, m, P;
int L1, L2;
int d[MX*2][2];
int dis[MX][2];
bool vist[MX][2];
bool f[MX][2]; 
vector<int> G[MX];

void dfs(int u, int pre){
    if(dis[u][pre] != -1) return;
    if(vist[u][pre]){
        dis[u][pre] = INF;
        return;
    }
    vist[u][pre] = 1;
    if(pre == 0 || G[u].size() == 1){
        int v = G[u][0];
        int nxt = G[v][0] == u;
        dfs(v, nxt);
        dis[u][pre] = dis[v][nxt] + 1;
        f[u][pre] |= f[v][nxt];
    }
    else{
        int v = G[u][1];
        int nxt = G[v][0] == u;
        dfs(v, nxt);
        dis[u][pre] = dis[v][nxt] + 1;
        f[u][pre] |= f[v][nxt];
    }
}

void calcL2(){
    memset(vist, 0, sizeof vist);
    int u = P, pre = 0;
    do{
        if(vist[u][pre]){
            L2 = INF;
            break;
        }
        L2++;
        vist[u][pre] = 1;
        if(pre == 0 || G[u].size() == 1){
            int v = G[u][0];
            int nxt = G[v][0] == u;
            u = v, pre = nxt;
        }
        else{
            int v = G[u][1];
            int nxt = G[v][0] == u;
            u = v, pre = nxt;
        }
    } while(u != P);
}

void calcL1(){
    memset(vist, 0, sizeof vist);
    int u = P, pre = 1;
    do{
        if(vist[u][pre]){
            L1 = INF;
            break;
        }
        L1++;
        vist[u][pre] = 1;
        if(pre == 0 || G[u].size() == 1){
            int v = G[u][0];
            int nxt = G[v][0] == u;
            u = v, pre = nxt;
        }
        else{
            int v = G[u][1];
            int nxt = G[v][0] == u;
            u = v, pre = nxt;
        }
    } while(u != P);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int QR[]){
    n = N;
    m = M;
    ::P = ++P;
    for(int i=0; i<M; i++){
        int u = R[i][0] + 1;
        int v = R[i][1] + 1;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    memset(dis, -1, sizeof dis);
    dis[P][0] = dis[P][1] = 0;
    f[P][1] = 1;
    for(int i=1; i<=n; i++) dfs(i, 0);
    calcL2();
    calcL1();

    set<int> st;
    for(int i=1; i<=n; i++) if(dis[i][0] < INF){
        d[dis[i][0]][f[i][0]]++;
        st.insert(dis[i][0]);
    }
    
    for(int i=0; i<Q; i++){
        int k = QR[i];
        int res = 0;
        for(int x: st){
            if(x > k) break;
            if((k - x)%L1 == 0) res += d[x][1];
            if((k - x)%L2 == 0) res += d[x][0];
        }
        answer(res);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5464 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5720 KB Output is correct
7 Correct 2 ms 5248 KB Output is correct
8 Correct 3 ms 5296 KB Output is correct
9 Correct 3 ms 5724 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5464 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5720 KB Output is correct
7 Correct 2 ms 5248 KB Output is correct
8 Correct 3 ms 5296 KB Output is correct
9 Correct 3 ms 5724 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct
11 Correct 7 ms 6856 KB Output is correct
12 Correct 15 ms 7988 KB Output is correct
13 Incorrect 33 ms 14432 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5464 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5720 KB Output is correct
7 Correct 2 ms 5248 KB Output is correct
8 Correct 3 ms 5296 KB Output is correct
9 Correct 3 ms 5724 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct
11 Correct 7 ms 6856 KB Output is correct
12 Correct 15 ms 7988 KB Output is correct
13 Incorrect 33 ms 14432 KB Output isn't correct
14 Halted 0 ms 0 KB -