Submission #969843

#	Time	Username	Problem	Language	Result	Execution time	Memory
969843		codefox	Tropical Garden (IOI11_garden)	C++14	100 / 100	2163 ms	13904 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

#define arr array<int, 2>

vector<arr> graph;
vector<arr> vis;
vector<arr> dist1;
vector<arr> dist2;
int starti, starts;

int next(int i, int state)
{
    if (state==0) 
    {
        int b = 0;
        if (i==graph[graph[i][0]][0]) b= 1;
        return b;
    }
    else 
    {
        int b = 0;
        if (i==graph[graph[i][1]][0]) b= 1;
        return b;
    }
}

int fcycle(int i, int state)
{
    if (vis[i][state])
    {
        if (i == starti && state == starts) return 0;
        else return 2*-1e9;
    }
    vis[i][state] = 1;
    if (state==0) return fcycle(graph[i][0], next(i,state))+1;
    else return fcycle(graph[i][1], next(i,state))+1;
}

int dfs1(int i, int state)
{
    if (vis[i][state]) return dist1[i][state];
    vis[i][state] = 1;
    if (state==0) dist1[i][state] = dfs1(graph[i][0], next(i,state))+1;
    else dist1[i][state] = dfs1(graph[i][1], next(i,state))+1;
    return dist1[i][state];
}

int dfs2(int i, int state)
{
    if (vis[i][state]) return dist2[i][state];
    vis[i][state] = 1;
    if (state==0) dist2[i][state] = dfs2(graph[i][0], next(i,state))+1;
    else dist2[i][state] = dfs2(graph[i][1], next(i,state))+1;
    return dist2[i][state];
}

const int K = 2*1e9;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    graph.assign(N, {-1, -1});
    dist1.assign(N, {K, K});
    dist2.assign(N, {K, K});
    for (int i = 0; i < M; i++)
    {
        int r1 = R[i][0];
        int r2 = R[i][1];
        if (graph[r1][0]==-1) graph[r1][0] = r2;
        else if (graph[r1][1]==-1) graph[r1][1] = r2;

        if (graph[r2][0]==-1) graph[r2][0] = r1;
        else if (graph[r2][1]==-1) graph[r2][1] = r1;
    }
    for (int i = 0; i < N; i++)
    {
        if (graph[i][1]==-1) graph[i][1] = graph[i][0];
    }

    vis.assign(N, {0,0});
    starti = P;
    starts = 0;
    int f = fcycle(starti, starts);
    vis.assign(N, {0,0});
    starts = 1;
    int s = fcycle(starti, starts);    

    vis.assign(N, {0,0});
    dist1[P][0] = 0;
    vis[P][0] = 1;
    for (int i = 0; i < N; i++)
    {
        dfs1(i, 0);
    }
    vis.assign(N, {0,0});
    dist2[P][1] = 0;
    vis[P][1] = 1;
    for (int i = 0; i < N; i++)
    {
        dfs2(i, 0);
    }

    for (int i = 0; i < Q; i++)
    {
        int ans=0;
        for (int j = 0; j < N; j++)
        {
            int b = 0;
            if (G[i]-dist1[j][0]>=0 && (G[i]-dist1[j][0])%f==0) b=1;
            if (G[i]-dist2[j][0]>=0 && (G[i]-dist2[j][0])%s==0) b=1;
            ans +=b;
        }
        answer(ans);
        //cout << ans;
    }
}

/*
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n, m, p, q;
    cin >> n >> m >> p >> q;
    int R[m][2];
    int G[q];
    for (int i = 0; i < m; i++) cin >> R[i][0] >> R[i][1];
    for (int i = 0; i < q; i++) cin >> G[i];
    count_routes(n, m, p, R, q, G);

    return 0;
}
*/

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31