oj.uz

Submission #164696

# Submission time Handle Problem Language Result Execution time Memory
164696 2019-11-22T16:23:08 Z arnold518 Tropical Garden (IOI11_garden) C++14
0 / 100
 17 ms 16888 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, M, P, Q;
int *G;
vector<int> adj2[MAXN+10];
vector<int> adj[MAXN+10];

int ans[MAXN+10];
int cnt[MAXN+10], cyc=-1;
int dep[MAXN+10];

void dfs(int now, int depth)
{
    //printf("%d\n", now);
    dep[now]=depth;
    for(auto nxt : adj[now])
    {
        if(dep[nxt]!=0)
        {
            cyc=depth+1-dep[nxt];
            continue;
        }
        dfs(nxt, depth+1);
    }
}

void count_routes(int _N, int _M, int _P, int R[][2], int _Q, int *_G)
{
    int i, j;
    N=_N; M=_M; P=_P; Q=_Q; G=_G;

    for(i=0; i<M; i++)
    {
        int u=R[i][0], v=R[i][1];
        adj2[u].push_back(v);
        adj2[v].push_back(u);
    }

    for(i=0; i<N; i++)
    {
        int nxt=adj2[i][0];
        if(adj2[nxt][0]==i) adj[nxt+N].push_back(i);//, printf("E%d %d\n", nxt+N, i);
        else adj[nxt].push_back(i);//, printf("E%d %d\n", nxt, i);
    }

    for(i=0; i<N; i++)
    {
        int nxt;
        if(adj2[i].size()==1) nxt=adj2[i][0];
        else nxt=adj2[i][1];

        if(adj2[nxt][0]==i) adj[nxt+N].push_back(i+N);//, printf("E%d %d\n", nxt+N, i+N);
        else adj[nxt].push_back(i+N);//, printf("E%d %d\n", nxt, i+N);
    }

    memset(cnt, 0, sizeof(cnt));
    memset(dep, 0, sizeof(dep));
    cyc=-1;
    dfs(P, 0);
    for(i=0; i<N; i++) cnt[dep[i]]++;

    for(i=0; i<Q; i++)
    {
        if(cyc==-1)
        {
            if(G[i]<2*N) ans[i]+=cnt[G[i]];
        }
        else
        {
            for(j=G[i]%cyc; j<2*N; j+=cyc) ans[i]+=cnt[j];
        }
    }

    //printf("!%d\n", cyc);

    memset(cnt, 0, sizeof(cnt));
    memset(dep, 0, sizeof(dep));
    cyc=-1;
    dfs(P+N, 0);
    for(i=0; i<N; i++) cnt[dep[i]]++;

    for(i=0; i<Q; i++)
    {
        if(cyc==-1)
        {
            if(G[i]<2*N) ans[i]+=cnt[G[i]];
        }
        else
        {
            for(j=G[i]%cyc; j<2*N; j+=cyc) ans[i]+=cnt[j];
        }
    }

    //printf("!%d\n", cyc);
    for(i=0; i<Q; i++) answer(ans[i]);
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 16888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 16888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 16888 KB Output isn't correct
2 Halted 0 ms 0 KB -