oj.uz

Submission #543319

# Submission time Handle Problem Language Result Execution time Memory
543319 2022-03-30T07:50:33 Z AmirElarbi Tropical Garden (IOI11_garden) C++14
69 / 100
 4513 ms 21616 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)
        f1[i] = INF, f2[i] = INF;
    for (int i = 0; i < n; ++i)
    {
        if(adj[i+n] == -1) adj[i+n] = adj[i];
    }
    for (int i = 0; i < 2*n; ++i)
    {
        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 4 ms 8916 KB Output is correct
3 Correct 4 ms 8916 KB Output is correct
4 Correct 4 ms 8780 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 5 ms 8788 KB Output is correct
9 Correct 6 ms 8944 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 4 ms 8916 KB Output is correct
3 Correct 4 ms 8916 KB Output is correct
4 Correct 4 ms 8780 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 5 ms 8788 KB Output is correct
9 Correct 6 ms 8944 KB Output is correct
10 Correct 5 ms 8788 KB Output is correct
11 Correct 11 ms 10324 KB Output is correct
12 Correct 19 ms 11128 KB Output is correct
13 Correct 34 ms 21404 KB Output is correct
14 Correct 62 ms 16496 KB Output is correct
15 Correct 81 ms 16732 KB Output is correct
16 Correct 63 ms 14736 KB Output is correct
17 Correct 50 ms 13836 KB Output is correct
18 Correct 19 ms 11104 KB Output is correct
19 Correct 60 ms 16616 KB Output is correct
20 Correct 85 ms 16724 KB Output is correct
21 Correct 56 ms 14716 KB Output is correct
22 Correct 54 ms 13856 KB Output is correct
23 Correct 61 ms 17316 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 4 ms 8916 KB Output is correct
3 Correct 4 ms 8916 KB Output is correct
4 Correct 4 ms 8780 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 5 ms 8788 KB Output is correct
9 Correct 6 ms 8944 KB Output is correct
10 Correct 5 ms 8788 KB Output is correct
11 Correct 11 ms 10324 KB Output is correct
12 Correct 19 ms 11128 KB Output is correct
13 Correct 34 ms 21404 KB Output is correct
14 Correct 62 ms 16496 KB Output is correct
15 Correct 81 ms 16732 KB Output is correct
16 Correct 63 ms 14736 KB Output is correct
17 Correct 50 ms 13836 KB Output is correct
18 Correct 19 ms 11104 KB Output is correct
19 Correct 60 ms 16616 KB Output is correct
20 Correct 85 ms 16724 KB Output is correct
21 Correct 56 ms 14716 KB Output is correct
22 Correct 54 ms 13856 KB Output is correct
23 Correct 61 ms 17316 KB Output is correct
24 Correct 5 ms 8788 KB Output is correct
25 Correct 79 ms 10240 KB Output is correct
26 Correct 96 ms 11216 KB Output is correct
27 Correct 2192 ms 21616 KB Output is correct
28 Incorrect 4513 ms 16716 KB Output isn't correct
29 Halted 0 ms 0 KB -