oj.uz

Submission #971537

# Submission time Handle Problem Language Result Execution time Memory
971537 2024-04-28T19:24:05 Z fzyzzz_z Tropical Garden (IOI11_garden) C++17
0 / 100
 4 ms 15228 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) {
    c2[d] += val[x]; 
    if (x == f) return; 
    for (auto u: r[x]) {
        dfs_c2(u, d + 1, f); 
    }
}

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(1 <= co && co <= 2); 

    for (auto x: c) {
        if (p[x] == 0) {
            dfs_c1(x, 0); 
        } else {
            dfs_c2(x, 0, g[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);

    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; 

        if (v < 2 * M) {
            answer(c1[v] + c2[v]); 
        } else {
            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:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int i = 1; i < adj[x].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 4 ms 15192 KB Output is correct
3 Correct 4 ms 15192 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 15228 KB Output is correct
7 Correct 3 ms 14936 KB Output is correct
8 Incorrect 4 ms 15192 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 4 ms 15192 KB Output is correct
3 Correct 4 ms 15192 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 15228 KB Output is correct
7 Correct 3 ms 14936 KB Output is correct
8 Incorrect 4 ms 15192 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 4 ms 15192 KB Output is correct
3 Correct 4 ms 15192 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 15228 KB Output is correct
7 Correct 3 ms 14936 KB Output is correct
8 Incorrect 4 ms 15192 KB Output isn't correct
9 Halted 0 ms 0 KB -