oj.uz

Submission #1017999

# Submission time Handle Problem Language Result Execution time Memory
1017999 2024-07-09T12:29:13 Z PAndaS Tropical Garden (IOI11_garden) C++14
49 / 100
 44 ms 54708 KB 
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define pib pair<int, bool>

using namespace std;

void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
    vector<vector<pair<int, int>>> gr(n, vector<pair<int, int>>(0));

    for(int i = 0; i < m; i++){
        gr[r[i][0]].push_back(pair<int, int>(i, r[i][1]));
        gr[r[i][1]].push_back(pair<int, int>(i, r[i][0]));
    }

    vector< vector< vector<pib> > > jmp(n, vector< vector<pib> >(18, vector<pib>(2)));

    for(int i = 0; i < n; i++){
        if(!gr[i].size()){
            jmp[i][0][0] = pib(i, 1);
            jmp[i][0][1] = pib(i, 1);
        }
        jmp[i][0][0] = pib(gr[i][0].second, 0);
        if(gr[jmp[i][0][0].first][0].second == i){
            jmp[i][0][0].second = 1;
        }
        if(gr[i].size() == 1)  jmp[i][0][1] = jmp[i][0][0];
        else{
            jmp[i][0][1] = pib(gr[i][1].second, 0);
            if(gr[jmp[i][0][1].first][0].second == i) jmp[i][0][1].second = 1;
        }
    }

    for(int j = 1; j < 18; j++){
        for(int i = 0; i < n; i++){
            jmp[i][j][0] = jmp[jmp[i][j - 1][0].first][j - 1][jmp[i][j - 1][0].second];
            jmp[i][j][1] = jmp[jmp[i][j - 1][1].first][j - 1][jmp[i][j - 1][1].second];
        }
    }
    int cur_n, cur_s, cnt = 0, tmp, tmp2, tmp3, tmp4;

    for(int i = 0; i < q; i++){
        cnt = 0;
        for(int j = 0; j < n; j++){
            tmp = g[i];
            cur_n = j;
            cur_s = 0;
            tmp2 = 0;
            while(tmp){
                if(tmp & (1 << tmp2)){
                    tmp3 = cur_n;
                    tmp4 = cur_s;
                    cur_n = jmp[tmp3][tmp2][tmp4].first;
                    cur_s = jmp[tmp3][tmp2][tmp4].second;
                    tmp -= (1 << tmp2);
                }
                tmp2++;
            }
            if(cur_n == p) cnt++;
        }
        answer(cnt);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1480 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 2 ms 1736 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1480 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 2 ms 1736 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Runtime error 44 ms 54708 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1480 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 2 ms 1736 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Runtime error 44 ms 54708 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -