oj.uz

Submission #39549

# Submission time Handle Problem Language Result Execution time Memory
39549 2018-01-16T12:32:54 Z smu201111192 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 55824 KB 
#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 500005;
vector<pair<int,int>> adj[MAXN];
int nxt[MAXN][30];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{

    for(int i=0;i<M;i++){
        adj[R[i][0]].push_back({i,R[i][1]});
        adj[R[i][1]].push_back({i,R[i][0]});
    }
    for(int i=0;i<N;i++){
        sort(adj[i].begin(),adj[i].end());
    }
    for(int i=0;i<N;i++){
        int here = i;
        int there = adj[i][0].second;
        nxt[i][0] = adj[i][0].second;
        if(adj[there][0].second == here) nxt[here][0] += N;
        there = nxt[i+N][0] = (adj[i].size() == 1) ? adj[i][0].second : adj[i][1].second;
        here = i + N;
        if(adj[there][0].second == here-N) nxt[here][0] += N;
    }
    for(int i=1;i<30;i++){
        for(int j=0;j<2*N;j++){
            nxt[j][i] = nxt[nxt[j][i-1]][i-1];
        }
    }
    for(int k=0;k<Q;k++){  // 반
        int cnt = 0;
        for(int i=0;i<N;i++){ //시작점
            int bit = G[k];
            int j = 0;
            int cur = i;
            while(bit){
                if(bit & (1<<j)){
                    bit -= (1<<j);
                    cur = nxt[cur][j];
                }
                j++;
            }
            if(cur == P || cur -N == P) cnt++;
        }
        answer(cnt);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12288 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 14 ms 12408 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 14 ms 12388 KB Output is correct
7 Correct 13 ms 12152 KB Output is correct
8 Correct 17 ms 12408 KB Output is correct
9 Correct 16 ms 12716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12288 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 14 ms 12408 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 14 ms 12388 KB Output is correct
7 Correct 13 ms 12152 KB Output is correct
8 Correct 17 ms 12408 KB Output is correct
9 Correct 16 ms 12716 KB Output is correct
10 Correct 13 ms 12132 KB Output is correct
11 Correct 36 ms 18512 KB Output is correct
12 Correct 61 ms 23672 KB Output is correct
13 Correct 107 ms 36452 KB Output is correct
14 Correct 260 ms 51892 KB Output is correct
15 Correct 256 ms 52548 KB Output is correct
16 Correct 180 ms 40960 KB Output is correct
17 Correct 140 ms 37336 KB Output is correct
18 Correct 60 ms 23652 KB Output is correct
19 Correct 244 ms 51880 KB Output is correct
20 Correct 245 ms 52536 KB Output is correct
21 Correct 165 ms 40816 KB Output is correct
22 Correct 137 ms 36968 KB Output is correct
23 Correct 279 ms 55824 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12288 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 14 ms 12408 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 14 ms 12388 KB Output is correct
7 Correct 13 ms 12152 KB Output is correct
8 Correct 17 ms 12408 KB Output is correct
9 Correct 16 ms 12716 KB Output is correct
10 Correct 13 ms 12132 KB Output is correct
11 Correct 36 ms 18512 KB Output is correct
12 Correct 61 ms 23672 KB Output is correct
13 Correct 107 ms 36452 KB Output is correct
14 Correct 260 ms 51892 KB Output is correct
15 Correct 256 ms 52548 KB Output is correct
16 Correct 180 ms 40960 KB Output is correct
17 Correct 140 ms 37336 KB Output is correct
18 Correct 60 ms 23652 KB Output is correct
19 Correct 244 ms 51880 KB Output is correct
20 Correct 245 ms 52536 KB Output is correct
21 Correct 165 ms 40816 KB Output is correct
22 Correct 137 ms 36968 KB Output is correct
23 Correct 279 ms 55824 KB Output is correct
24 Correct 17 ms 12152 KB Output is correct
25 Correct 3429 ms 18644 KB Output is correct
26 Execution timed out 5059 ms 23784 KB Time limit exceeded
27 Halted 0 ms 0 KB -