oj.uz

Submission #543320

# Submission time Handle Problem Language Result Execution time Memory
543320 2022-03-30T07:54:14 Z AmirElarbi Tropical Garden (IOI11_garden) C++14
69 / 100
 4476 ms 21584 KB 
#include <bits/stdc++.h>
#include "gardenlib.h"
#define ii pair<int,int>
#define ve vector
#define vi vector<int>
#define vii vector<ii>
#define pb push_back
#define fi first
#define MAX_N 500000
#define se second
#define eps 1e-7
#define INF 1e7
#define ll long long
#include "garden.h"
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int nax = 3e5+5;
using namespace std;
int n,m,p,q, aff = 0, cur,res,c1 = INF, c2 = INF;
vi rev[nax];
bool vis[nax];
int adj[nax], f1[nax], f2[nax];
void dfs(int u, int d){
    if(vis[u] && u == p){
        c1 = d;
        return;
    } else if(vis[u])
        return;
    f1[u] = d;
    vis[u] = 1;
    for(auto x : rev[u])
        dfs(x,d+1);
}
void dfs2(int u, int d){
    if(vis[u] && u == p+n){
        c2 = d;
        return;
    } else if(vis[u])
        return;
    f2[u] = d, vis[u] = 1;
    for(auto x : rev[u])
        dfs2(x,d+1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    n = N,m = M, p = P;
    memset(adj,-1,sizeof adj);
    for(int i = 0; i < m; i++){
        int a,b;
        a = R[i][0], b = R[i][1];
        if(adj[a] == -1) {
            if(adj[b] != -1){
                adj[a] = b;
                if(adj[b+n] == -1) adj[b+n] = a+n;
            } else {
                adj[a] = b+n, adj[b] = a+n;
            }
        } else if(adj[a+n] == -1){
            if(adj[b] != -1){
                adj[a+n] = b;
                if(adj[b+n] == -1) adj[b+n] = a;
            } else {
                adj[a+n] = b+n, adj[b] = a;
            }
        } else {
            if(adj[b] != -1){
                if(adj[b+n] == -1)
                    adj[b+n] = a;
            } else {
                adj[b] = a;
            }
        }
    }
    for (int i = 0; i < 2*n; ++i)
    {
        if(i < n && adj[i+n] == -1) adj[i+n] = adj[i];
        f1[i] = INF, f2[i] = INF;
        rev[adj[i]].pb(i);
    }
    dfs(p,0);
    memset(vis,0,sizeof vis);
    dfs2(p+n,0);
    q = Q;
    for(int i = 0; i < q; i++){
        aff = 0;
        cur = G[i];
        for (int j = 0; j < n; ++j)
        {
            if(c1 != INF && cur >= f1[j] && (cur-f1[j])%c1 == 0) aff++;
            else if(c2 != INF && cur >= f2[j]  && (cur-f2[j])%c2 == 0) aff++;
            else if(cur == f1[j]) aff++;
            else if(cur == f2[j]) aff++;
        }
        answer(aff);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 5 ms 8852 KB Output is correct
3 Correct 4 ms 8916 KB Output is correct
4 Correct 4 ms 8788 KB Output is correct
5 Correct 4 ms 8788 KB Output is correct
6 Correct 4 ms 8916 KB Output is correct
7 Correct 4 ms 8788 KB Output is correct
8 Correct 4 ms 8788 KB Output is correct
9 Correct 5 ms 8960 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 5 ms 8852 KB Output is correct
3 Correct 4 ms 8916 KB Output is correct
4 Correct 4 ms 8788 KB Output is correct
5 Correct 4 ms 8788 KB Output is correct
6 Correct 4 ms 8916 KB Output is correct
7 Correct 4 ms 8788 KB Output is correct
8 Correct 4 ms 8788 KB Output is correct
9 Correct 5 ms 8960 KB Output is correct
10 Correct 4 ms 8788 KB Output is correct
11 Correct 11 ms 10324 KB Output is correct
12 Correct 20 ms 11092 KB Output is correct
13 Correct 38 ms 21360 KB Output is correct
14 Correct 63 ms 16584 KB Output is correct
15 Correct 89 ms 16824 KB Output is correct
16 Correct 57 ms 14660 KB Output is correct
17 Correct 56 ms 13844 KB Output is correct
18 Correct 21 ms 11220 KB Output is correct
19 Correct 60 ms 16492 KB Output is correct
20 Correct 83 ms 16656 KB Output is correct
21 Correct 60 ms 14720 KB Output is correct
22 Correct 56 ms 13944 KB Output is correct
23 Correct 60 ms 17248 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 5 ms 8852 KB Output is correct
3 Correct 4 ms 8916 KB Output is correct
4 Correct 4 ms 8788 KB Output is correct
5 Correct 4 ms 8788 KB Output is correct
6 Correct 4 ms 8916 KB Output is correct
7 Correct 4 ms 8788 KB Output is correct
8 Correct 4 ms 8788 KB Output is correct
9 Correct 5 ms 8960 KB Output is correct
10 Correct 4 ms 8788 KB Output is correct
11 Correct 11 ms 10324 KB Output is correct
12 Correct 20 ms 11092 KB Output is correct
13 Correct 38 ms 21360 KB Output is correct
14 Correct 63 ms 16584 KB Output is correct
15 Correct 89 ms 16824 KB Output is correct
16 Correct 57 ms 14660 KB Output is correct
17 Correct 56 ms 13844 KB Output is correct
18 Correct 21 ms 11220 KB Output is correct
19 Correct 60 ms 16492 KB Output is correct
20 Correct 83 ms 16656 KB Output is correct
21 Correct 60 ms 14720 KB Output is correct
22 Correct 56 ms 13944 KB Output is correct
23 Correct 60 ms 17248 KB Output is correct
24 Correct 5 ms 8788 KB Output is correct
25 Correct 81 ms 10304 KB Output is correct
26 Correct 111 ms 11204 KB Output is correct
27 Correct 2191 ms 21584 KB Output is correct
28 Incorrect 4476 ms 16632 KB Output isn't correct
29 Halted 0 ms 0 KB -