oj.uz

Submission #971539

# Submission time Handle Problem Language Result Execution time Memory
971539 2024-04-28T19:51:45 Z fzyzzz_z Tropical Garden (IOI11_garden) C++17
49 / 100
 408 ms 88616 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(); 
        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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 4 ms 15196 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 14940 KB Output is correct
8 Correct 4 ms 15196 KB Output is correct
9 Correct 12 ms 16220 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 4 ms 15196 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 14940 KB Output is correct
8 Correct 4 ms 15196 KB Output is correct
9 Correct 12 ms 16220 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 26 ms 20312 KB Output is correct
12 Correct 88 ms 25808 KB Output is correct
13 Correct 117 ms 48208 KB Output is correct
14 Correct 370 ms 49216 KB Output is correct
15 Correct 383 ms 50256 KB Output is correct
16 Correct 367 ms 45288 KB Output is correct
17 Correct 353 ms 43724 KB Output is correct
18 Correct 100 ms 25748 KB Output is correct
19 Correct 363 ms 49520 KB Output is correct
20 Correct 396 ms 50464 KB Output is correct
21 Correct 408 ms 45224 KB Output is correct
22 Runtime error 369 ms 88616 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 4 ms 15196 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 14940 KB Output is correct
8 Correct 4 ms 15196 KB Output is correct
9 Correct 12 ms 16220 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 26 ms 20312 KB Output is correct
12 Correct 88 ms 25808 KB Output is correct
13 Correct 117 ms 48208 KB Output is correct
14 Correct 370 ms 49216 KB Output is correct
15 Correct 383 ms 50256 KB Output is correct
16 Correct 367 ms 45288 KB Output is correct
17 Correct 353 ms 43724 KB Output is correct
18 Correct 100 ms 25748 KB Output is correct
19 Correct 363 ms 49520 KB Output is correct
20 Correct 396 ms 50464 KB Output is correct
21 Correct 408 ms 45224 KB Output is correct
22 Runtime error 369 ms 88616 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -