oj.uz

Submission #405304

# Submission time Handle Problem Language Result Execution time Memory
405304 2021-05-16T07:45:25 Z Andyvanh1 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 62916 KB 
#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

#define vt vector
#define pb push_back
#define all(x) x.begin(),x.end()

typedef vt<int> vi;
typedef long long ll;
typedef pair<int,int> pii;



vt<pair<int,int>> adjlist[150004];
vi adj[300008];
int nex[300008][31];

void gennex(){
    for(int j = 1; j < 31; j++){
        for(int i = 0; i < 300008; i++){
            if(nex[i][j-1]==-1){
                nex[i][j] = -1;
            }else{
                nex[i][j] = nex[nex[i][j-1]][j-1];
            }
        }
    }
}

int get(int i, int jmp){
    for(int j = 0; j < 31; j++){
        if(jmp&(1<<j)){
            i = nex[i][j];
        }
    }
    return i;
}

void count_routes(int n, int m, int p,int r[][2],int q,int g[]){
    for(int i = 0; i < m; i++){
        adjlist[r[i][0]].pb({i,r[i][1]});
        adjlist[r[i][1]].pb({i,r[i][0]});
    }
    for(int i = 0; i < n; i++){
        sort(all(adjlist[i]));
    }

    for(int i = 0; i < n; i++){
        int j1 = adjlist[i][0].second;
        if(adjlist[i].size()==1){
            if(adjlist[j1].size()==1){
                adj[i].pb(j1);
            }else if(adjlist[j1][0].second == i){
                adj[i].pb(n+j1);
            }else{
                adj[i].pb(j1);
            }
            continue;
        }

        if(adjlist[j1].size()==1){
            adj[i].pb(j1);
        }else if(adjlist[j1][0].second == i){
            adj[i].pb(n+j1);
        }else{
            adj[i].pb(j1);
        }

        int j2 = adjlist[i][1].second;
        if(adjlist[j2].size()==1){
            adj[i+n].pb(j2);
        }else if(adjlist[j2][0].second == i){
            adj[i+n].pb(n+j2);
        }else{
            adj[i+n].pb(j2);
        }


    }

    for(int i = 0; i < 2*n; i++){
        if(adj[i].empty()){
            nex[i][0] = -1;
        }else{
            nex[i][0] = adj[i][0];
        }
    }
    gennex();


    for(int i = 0; i < q; i++){
        int x = g[i];
        int ans = 0;
        for(int j = 0; j < n; j++){
            if(get(j,x)==p||get(j,x)==p+n){
                ans++;
            }
        }
        answer(ans);


    }

}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 47340 KB Output is correct
2 Correct 128 ms 47368 KB Output is correct
3 Correct 129 ms 47332 KB Output is correct
4 Correct 130 ms 47372 KB Output is correct
5 Correct 133 ms 47268 KB Output is correct
6 Correct 135 ms 47360 KB Output is correct
7 Correct 130 ms 47272 KB Output is correct
8 Correct 125 ms 47352 KB Output is correct
9 Correct 128 ms 47644 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 47340 KB Output is correct
2 Correct 128 ms 47368 KB Output is correct
3 Correct 129 ms 47332 KB Output is correct
4 Correct 130 ms 47372 KB Output is correct
5 Correct 133 ms 47268 KB Output is correct
6 Correct 135 ms 47360 KB Output is correct
7 Correct 130 ms 47272 KB Output is correct
8 Correct 125 ms 47352 KB Output is correct
9 Correct 128 ms 47644 KB Output is correct
10 Correct 133 ms 47336 KB Output is correct
11 Correct 139 ms 49568 KB Output is correct
12 Correct 154 ms 51988 KB Output is correct
13 Correct 187 ms 56836 KB Output is correct
14 Correct 278 ms 61744 KB Output is correct
15 Correct 290 ms 62180 KB Output is correct
16 Correct 246 ms 59392 KB Output is correct
17 Correct 211 ms 58356 KB Output is correct
18 Correct 163 ms 51900 KB Output is correct
19 Correct 274 ms 61776 KB Output is correct
20 Correct 267 ms 62180 KB Output is correct
21 Correct 234 ms 59260 KB Output is correct
22 Correct 227 ms 58436 KB Output is correct
23 Correct 272 ms 62916 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 47340 KB Output is correct
2 Correct 128 ms 47368 KB Output is correct
3 Correct 129 ms 47332 KB Output is correct
4 Correct 130 ms 47372 KB Output is correct
5 Correct 133 ms 47268 KB Output is correct
6 Correct 135 ms 47360 KB Output is correct
7 Correct 130 ms 47272 KB Output is correct
8 Correct 125 ms 47352 KB Output is correct
9 Correct 128 ms 47644 KB Output is correct
10 Correct 133 ms 47336 KB Output is correct
11 Correct 139 ms 49568 KB Output is correct
12 Correct 154 ms 51988 KB Output is correct
13 Correct 187 ms 56836 KB Output is correct
14 Correct 278 ms 61744 KB Output is correct
15 Correct 290 ms 62180 KB Output is correct
16 Correct 246 ms 59392 KB Output is correct
17 Correct 211 ms 58356 KB Output is correct
18 Correct 163 ms 51900 KB Output is correct
19 Correct 274 ms 61776 KB Output is correct
20 Correct 267 ms 62180 KB Output is correct
21 Correct 234 ms 59260 KB Output is correct
22 Correct 227 ms 58436 KB Output is correct
23 Correct 272 ms 62916 KB Output is correct
24 Correct 141 ms 47292 KB Output is correct
25 Execution timed out 5073 ms 49676 KB Time limit exceeded
26 Halted 0 ms 0 KB -