oj.uz

Submission #584745

# Submission time Handle Problem Language Result Execution time Memory
584745 2022-06-28T01:25:48 Z perchuts Tropical Garden (IOI11_garden) C++17
49 / 100
 189 ms 66380 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "garden.h"
#include "gardenlib.h"
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<int>g[maxn], ciclo[maxn], g2[maxn];

int n, f[maxn], dist[maxn], vis[maxn], res[maxn];

// void answer(int x){cout<<x<<endl;}

void dfs(int u,int d){
    vis[u] = 2;
    dist[u] = d;
    for(auto v:g2[u]){
        if(vis[v]!=2)dfs(v,d+1);
    }
}

void compute(int P, int Q,int G[]){
    for(int i=0;i<=2*n;++i){
        vis[i] = dist[i] = 0;
        ciclo[i].clear();
    }
    int cur = P, tciclo = 0;
    while(vis[cur]==0){
        vis[cur] = 1, cur = f[cur];
    }
    while(vis[cur]==1){
        vis[cur] = 2, cur = f[cur], ++tciclo;
    }
    //achei o ciclo da componente de p
    if(vis[P]==1){
        tciclo = 1e9, vis[f[P]] = 2;
        dfs(P,0);
        vis[f[P]] = 0;
    }else{
        cur = P;
        int d = tciclo;
        do{
            dfs(cur, d%tciclo), cur = f[cur], d--;
        } while(cur!=P);
        if(P<n)ciclo[0].pb(tciclo);
    }
    for(int i=0;i<n;++i){
        if(vis[i]&&dist[i]){
            ciclo[dist[i]%tciclo].pb(dist[i]);                
        }
    }
    for(int i=0;i<min(tciclo,3*n);++i){
        sort(all(ciclo[i]));
    }
    for(int i=0;i<Q;++i){
        int cur = G[i], ans = upper_bound(all(ciclo[cur%tciclo]),cur) - begin(ciclo[cur%tciclo]);
        res[i] += ans;
    }
    
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n = N;
    for(int i=0;i<M;++i){
        int u = R[i][0], v = R[i][1];
        g[u].pb(v), g[v].pb(u);
    }
    //grafo funcional, achar distancia de cada vertice pra p   
    for(int i=0;i<2*n;++i){
        int act = i%n;
        if(i<n||sz(g[act])==1){
            int best = g[act][0];
            if(g[best][0]==act)f[i] = best+n;
            else f[i] = best;
        }else{
            if(g[g[act][1]][0]==act)f[i] = g[act][1] + n;
            else f[i] = g[act][1];
        }
        g2[i].pb(f[i]), g2[f[i]].pb(i);
        // cout<<i<<" "<<f[i]<<endl;
    }

    compute(P,Q,G), compute(P+n,Q,G);

    for(int i=0;i<Q;++i){
        answer(res[i]);
    }
}

// int v[maxn][2], queries[maxn];

// int main(){
//     int n,m,p,q;cin>>n>>m>>p>>q;
//     for(int i=0;i<m;++i){
//         cin>>v[i][0]>>v[i][1];
//     }
//     for(int i=0;i<q;++i)cin>>queries[i];
//     count_routes(n,m,p,v,q,queries);
// }

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21588 KB Output is correct
2 Correct 11 ms 21576 KB Output is correct
3 Correct 11 ms 21644 KB Output is correct
4 Correct 10 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 12 ms 21632 KB Output is correct
7 Correct 11 ms 21460 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Correct 12 ms 21728 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21588 KB Output is correct
2 Correct 11 ms 21576 KB Output is correct
3 Correct 11 ms 21644 KB Output is correct
4 Correct 10 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 12 ms 21632 KB Output is correct
7 Correct 11 ms 21460 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Correct 12 ms 21728 KB Output is correct
10 Correct 11 ms 21460 KB Output is correct
11 Correct 21 ms 24532 KB Output is correct
12 Correct 36 ms 26960 KB Output is correct
13 Correct 54 ms 35700 KB Output is correct
14 Correct 155 ms 40728 KB Output is correct
15 Correct 189 ms 41672 KB Output is correct
16 Correct 112 ms 35924 KB Output is correct
17 Runtime error 102 ms 66380 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21588 KB Output is correct
2 Correct 11 ms 21576 KB Output is correct
3 Correct 11 ms 21644 KB Output is correct
4 Correct 10 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 12 ms 21632 KB Output is correct
7 Correct 11 ms 21460 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Correct 12 ms 21728 KB Output is correct
10 Correct 11 ms 21460 KB Output is correct
11 Correct 21 ms 24532 KB Output is correct
12 Correct 36 ms 26960 KB Output is correct
13 Correct 54 ms 35700 KB Output is correct
14 Correct 155 ms 40728 KB Output is correct
15 Correct 189 ms 41672 KB Output is correct
16 Correct 112 ms 35924 KB Output is correct
17 Runtime error 102 ms 66380 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -