oj.uz

답안 #1108129

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1108129 2024-11-02T23:54:59 Z laight 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
49 / 100
 31 ms 22740 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pi pair<int, int>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pll pair<ll, ll>
#define umi unordered_map<int, int>
#define umll unordered_map<ll, ll>
#define umllv unordered_map<ll, vector<ll>>
 
#define getchar() (*_pinp?*_pinp++:(_inp[fread(_pinp=_inp, 1, 4096, stdin)]='\0', *_pinp++))
char _inp[4097], *_pinp=_inp;
#define scan(x) do{while((x=getchar())<'-'); _ssign=x=='-'; if(_ssign) while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0'); x=_ssign?-x:x;}while(0)
char _; bool _ssign;
 
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
 
using namespace std; using namespace __gnu_pbds;
 
const int MM = 1e5+5e4+5;
const ll inf = 2e15+1;
const int lg = 17; // 17 for 1e5, 31 for 1e9
 
int n, m, p, a, b, lv, cycl, cl1, cl2, q, inp; bool cvis[2*MM], vis[2*MM], vis2[2*MM], hcy, cy1, cy2;
vector<int> g(2005), ans(2005), to(2*MM), rev[2*MM], graph[MM], dis, dis2;
 
void g_f(int c, vector<int> &dv){
    queue<pi> q; q.push({0, c});
    while (!q.empty()){
        int cur = q.front().se, cd = q.front().fi;
        q.pop();
      	if (vis[cur]) continue;
      	vis[cur] = 1;
        if (cur < n) dv.pb(cd);
        for (int i : rev[cur]){
            if (!vis[i]){
                q.push({cd+1, i});
            }
        }
    }
}
void cyc_f(int c, int d, int pe){
    if (cvis[c]){
        if (c == pe) {hcy = 1; cycl = d;}
        return;
    }
    cvis[c] = 1; cyc_f(to[c], d+1, pe);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    // cin.tie(0); cin.sync_with_stdio(0);
    // freopen("changyue_tst.txt", "r", stdin);
    n = N; m = M; p = P;
    for (int i=0; i<m; ++i){
        graph[R[i][0]].pb(R[i][1]); graph[R[i][1]].pb(R[i][0]);
    }
    q = Q; for (int i=0; i<q; i++) {g[i] = G[i];}
    for (int i=0; i<n; ++i){
        int oth = graph[i][0];
        if (i == graph[oth][0]){
            to[i] = n+oth;
        }
        else {to[i] = oth;}
        if (graph[i].size() >= 2){
            int oth2 = graph[i][1];
            if (i == graph[oth2][0]){
                to[n+i] = n+oth2;
            }
            else {to[n+i] = oth2;}
        }
        else{
            if (i == graph[oth][0]){
                to[n+i] = n+oth;
            }
            else {to[n+i] = oth;}
        }
    }
    for (int i=0; i<2*n; i++){
        rev[to[i]].pb(i);
    }
    cl1 = cl2 = 0;
    hcy = 0; cycl = 0;
    cyc_f(p, 0, p);
    cl1 = cycl; cy1 = hcy;
    memset(cvis, 0, sizeof(cvis));
    hcy = 0; cycl = 0;
    cyc_f(n+p, 0, n+p);
    cl2 = cycl; cy2 = hcy;
    g_f(p, dis); g_f(n+p, dis2);
    for (int i=0; i<q; ++i){
        int tv=g[i], ca=0;
        for (int j : dis){
            if (j > tv) break;
            if (cl1){
                if (tv%cl1 == j%cl1) ++ca;
            }
            else{
                if (tv == j) ++ca;
            }
        }
        for (int j : dis2){
            if (j > tv) break;
            if (cl2){
                if (tv%cl2 == j%cl2) ++ca;
            }
            else{
                if (tv == j) ++ca;
            }
        }
        answer(ca);
    }
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14160 KB Output is correct
2 Correct 4 ms 14116 KB Output is correct
3 Correct 3 ms 14160 KB Output is correct
4 Correct 4 ms 13904 KB Output is correct
5 Correct 3 ms 13904 KB Output is correct
6 Correct 4 ms 14160 KB Output is correct
7 Correct 3 ms 13904 KB Output is correct
8 Correct 3 ms 14180 KB Output is correct
9 Correct 5 ms 14160 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14160 KB Output is correct
2 Correct 4 ms 14116 KB Output is correct
3 Correct 3 ms 14160 KB Output is correct
4 Correct 4 ms 13904 KB Output is correct
5 Correct 3 ms 13904 KB Output is correct
6 Correct 4 ms 14160 KB Output is correct
7 Correct 3 ms 13904 KB Output is correct
8 Correct 3 ms 14180 KB Output is correct
9 Correct 5 ms 14160 KB Output is correct
10 Correct 3 ms 13904 KB Output is correct
11 Correct 10 ms 15696 KB Output is correct
12 Correct 19 ms 16712 KB Output is correct
13 Incorrect 31 ms 22740 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14160 KB Output is correct
2 Correct 4 ms 14116 KB Output is correct
3 Correct 3 ms 14160 KB Output is correct
4 Correct 4 ms 13904 KB Output is correct
5 Correct 3 ms 13904 KB Output is correct
6 Correct 4 ms 14160 KB Output is correct
7 Correct 3 ms 13904 KB Output is correct
8 Correct 3 ms 14180 KB Output is correct
9 Correct 5 ms 14160 KB Output is correct
10 Correct 3 ms 13904 KB Output is correct
11 Correct 10 ms 15696 KB Output is correct
12 Correct 19 ms 16712 KB Output is correct
13 Incorrect 31 ms 22740 KB Output isn't correct
14 Halted 0 ms 0 KB -