oj.uz

답안 #586997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586997 2022-07-01T07:56:44 Z MohamedFaresNebili 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 48 ms 52044 KB 
#include <bits/stdc++.h>
#include "garden.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
 
        using namespace std;
 
        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;
 
        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound
 
        const int MOD = 1000 * 1000 * 1000 + 7;
 
        int to[150001][2];
        set<int> D[150001];
        map<int, int> vis[150001][2];
        vector<array<int, 2>> adj[150001];

		void answer(int X);
 
        void dfs(int v, int p, int state, int dep = 0) {
            if(dep >= 150000 || vis[v][dep][state]) return;
            D[dep].insert(v); vis[v][dep][state] = 1;
            for(auto u : adj[v]) {
                if(u[0] != p && u[1] == 0)
                    dfs(u[0], v, 0, dep + 1);
                else if(u[0] == p && u[1] == 1)
                    dfs(u[0], v, 1, dep + 1);
                else if(u[0] == p && to[u[0]][1] == -1)
                    dfs(u[0], v, 0, dep + 1);
            }
        }
 
        void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
            memset(to, -1, sizeof to);
            for(int l = 0; l < M; l++) {
                int u = R[l][0], v = R[l][1];
 
                if(to[u][0] == -1) to[u][0] = v;
                else if(to[u][0] != -1 && to[u][1] == -1) to[u][1] = v;
 
                if(to[v][0] == -1) to[v][0] = u;
                else if(to[v][0] != -1 && to[v][1] == -1) to[v][1] = u;
 
            }
 
            for(int l = 0; l < N; l++) {
                if(to[l][0] != -1)
                    adj[to[l][0]].pb({l, 0});
                if(to[l][1] != -1)
                    adj[to[l][1]].pb({l, 1});
            }
 
            dfs(P, P, 0, 0);
 
            for(int l = 0; l < Q; l++) {
                int v = G[l] % 150000;
                answer(D[v].size());
            }
        }

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 52044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 52044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 52044 KB Output isn't correct
2 Halted 0 ms 0 KB -