oj.uz

답안 #971538

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971538 2024-04-28T19:50:55 Z fzyzzz_z 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
49 / 100
 413 ms 90224 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

// void answer(int x) {
//     cout << "! " << x << '\n';
// }

using ll = long long; 

const int mxn = 150005; 

int g[2 * mxn], p[2 * mxn], vis[2 * mxn], c1[2 * mxn], c2[2 * mxn], val[2 * mxn]; 
vector<int> r[2 * mxn]; 

void dfs_find(int x) {
    if (vis[x]) return; 
    vis[x] = 1; 
    for (auto u: r[x]) {
        dfs_find(u); 
    }
    dfs_find(g[x]); 
}
void dfs_c1(int x, int d) {
    c1[d] += val[x];  
    for (auto u: r[x]) {
        dfs_c1(u, d + 1); 
    }
}
void dfs_c2(int x, int d, int f, int st) {
    c2[d] += val[x]; 
    // cout << "!! " << x << ' ' << d << ' ' << f << ' ' << val[x] << '\n';
    for (auto u: r[x]) {
        if (x == f && u == st) continue; 
        dfs_c2(u, d + 1, f, st); 
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    vector<vector<int>> adj(N); 
    map<pair<int, int>, int> to; 
    vector<int> c; 
    for (int i = 0; i < M; ++i) {
        int x = R[i][0], y = R[i][1]; 
        to[{x, y}] = 2 * i; 
        to[{y, x}] = 2 * i + 1; 
        val[2 * i] = val[2 * i + 1] = 0; 
        adj[x].push_back(y); 
        adj[y].push_back(x); 
        if (x == P) c.push_back(2 * i + 1); 
        if (y == P) c.push_back(2 * i); 
    }
    for (int x = 0; x < N; ++x) {
        for (int i = 1; i < adj[x].size(); ++i) {
            g[to[{adj[x][i], x}]] = to[{x, adj[x][0]}]; 
        }
        g[to[{adj[x][0], x}]] = to[{x, adj[x][min((int)adj[x].size(), 2) - 1]}]; 
        val[to[{x, adj[x][0]}]] = 1; 
    }
    for (int x = 0; x < 2 * M; ++x) {
        vis[x] = c1[x] = c2[x] = p[x] = 0; 
    }
    for (int x = 0; x < 2 * M; ++x) {
        r[g[x]].push_back(x); 
        p[g[x]]++; 
    }

    queue<int> q; 
    for (int i = 0; i < 2 * M; ++i) {
        if (p[i] == 0) {
            q.push(i); 
        }
    }
    while (q.size()) {
        auto x = q.front(); 
        // assert(vis[x]); 
        q.pop(); 
        p[g[x]]--; 
        if (p[g[x]] == 0) {
            q.push(g[x]); 
        }
    }

    
    int co = 0; 
    for (auto x: c) if (p[x]) co++; 
    assert(co <= 2); 



    for (auto x: c) {
        if (p[x] == 0) {
            dfs_c1(x, 0); 
        } else {
            dfs_c2(x, 0, g[x], x); 
        }
    }
    
    int clen = -1; 
    for (auto x: c) {
        if (p[x]) {
            int cnt = 1; 
            int y = g[x]; 
            while (y != x) {
                y = g[y]; 
                cnt++; 
            }
            assert(clen == cnt || clen == -1); 
            clen = cnt; 
        }
    }
    assert((clen == -1) == (co == 0));  

    for (int i = 0; i < 2 * M; ++i) {
        if (i + clen < 2 * M) {
            c2[i + clen] += c2[i]; 
        }
    }

    for (int i = 0; i < Q; ++i) {
        int v = G[i] - 1; 

        int cans = 0; 
        for (int st = 0; st < 2 * M; ++st) {
            if (val[st]) {
                int xx = st; 
                for (int t = 0; t < v; ++t) xx = g[xx]; 
                int ok = 0; 
                for (auto x: c) if (x == xx) ok = 1; 
                cans += ok; 
                // if (ok) cout << st << ' ';
            }
        }
        // cout << "\n! " << cans << '\n'; 

        // cout << c1[v] << ' ' << c2[v] << '\n';

        if (v < 2 * M) {
            answer(c1[v] + c2[v]); 
        } else {
            if (clen == -1) {
                answer(0); 
                continue; 
            }
            int f = (v - 2 * M) / clen; 
            v -= f * clen; 
            if (f > 0) v += clen; 
            while (v >= 2 * M) v -= clen; 
            answer(c2[v]); 
        }
    }
}

// int main() {
//     int n, m, p, q; 
//     cin >> n >> m >> p >> q; 
//     int e[m][2], g[q]; 
//     for (int i = 0; i < m; ++i) cin >> e[i][0] >> e[i][1]; 
//     for (int i = 0; i < q; ++i) cin >> g[i]; 
//     count_routes(n, m, p, e, q, g); 
// }

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 1; i < adj[x].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 4 ms 15196 KB Output is correct
3 Correct 4 ms 15192 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 5 ms 15452 KB Output is correct
7 Correct 3 ms 15096 KB Output is correct
8 Correct 4 ms 15192 KB Output is correct
9 Correct 12 ms 16472 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 4 ms 15196 KB Output is correct
3 Correct 4 ms 15192 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 5 ms 15452 KB Output is correct
7 Correct 3 ms 15096 KB Output is correct
8 Correct 4 ms 15192 KB Output is correct
9 Correct 12 ms 16472 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 26 ms 20540 KB Output is correct
12 Correct 96 ms 26416 KB Output is correct
13 Correct 104 ms 49156 KB Output is correct
14 Correct 327 ms 51032 KB Output is correct
15 Correct 410 ms 51944 KB Output is correct
16 Correct 401 ms 46928 KB Output is correct
17 Correct 356 ms 45392 KB Output is correct
18 Correct 83 ms 26372 KB Output is correct
19 Correct 340 ms 51332 KB Output is correct
20 Correct 413 ms 51948 KB Output is correct
21 Correct 391 ms 46932 KB Output is correct
22 Runtime error 326 ms 90224 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 4 ms 15196 KB Output is correct
3 Correct 4 ms 15192 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 5 ms 15452 KB Output is correct
7 Correct 3 ms 15096 KB Output is correct
8 Correct 4 ms 15192 KB Output is correct
9 Correct 12 ms 16472 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 26 ms 20540 KB Output is correct
12 Correct 96 ms 26416 KB Output is correct
13 Correct 104 ms 49156 KB Output is correct
14 Correct 327 ms 51032 KB Output is correct
15 Correct 410 ms 51944 KB Output is correct
16 Correct 401 ms 46928 KB Output is correct
17 Correct 356 ms 45392 KB Output is correct
18 Correct 83 ms 26372 KB Output is correct
19 Correct 340 ms 51332 KB Output is correct
20 Correct 413 ms 51948 KB Output is correct
21 Correct 391 ms 46932 KB Output is correct
22 Runtime error 326 ms 90224 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -