oj.uz

Submission #971540

# Submission time Handle Problem Language Result Execution time Memory
971540 2024-04-28T19:52:37 Z fzyzzz_z Tropical Garden (IOI11_garden) C++17
49 / 100
 386 ms 50260 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 4 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15192 KB Output is correct
4 Correct 2 ms 14936 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 15476 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 4 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15192 KB Output is correct
4 Correct 2 ms 14936 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 15476 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 3 ms 14936 KB Output is correct
11 Correct 26 ms 20052 KB Output is correct
12 Correct 81 ms 26188 KB Output is correct
13 Correct 112 ms 48208 KB Output is correct
14 Correct 321 ms 49360 KB Output is correct
15 Correct 358 ms 50260 KB Output is correct
16 Correct 345 ms 45448 KB Output is correct
17 Correct 326 ms 43688 KB Output is correct
18 Correct 98 ms 25940 KB Output is correct
19 Correct 334 ms 49232 KB Output is correct
20 Correct 386 ms 50260 KB Output is correct
21 Correct 342 ms 45140 KB Output is correct
22 Incorrect 346 ms 43856 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15192 KB Output is correct
4 Correct 2 ms 14936 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 15476 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 3 ms 14936 KB Output is correct
11 Correct 26 ms 20052 KB Output is correct
12 Correct 81 ms 26188 KB Output is correct
13 Correct 112 ms 48208 KB Output is correct
14 Correct 321 ms 49360 KB Output is correct
15 Correct 358 ms 50260 KB Output is correct
16 Correct 345 ms 45448 KB Output is correct
17 Correct 326 ms 43688 KB Output is correct
18 Correct 98 ms 25940 KB Output is correct
19 Correct 334 ms 49232 KB Output is correct
20 Correct 386 ms 50260 KB Output is correct
21 Correct 342 ms 45140 KB Output is correct
22 Incorrect 346 ms 43856 KB Output isn't correct
23 Halted 0 ms 0 KB -