oj.uz

답안 #116543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116543 2019-06-12T21:36:30 Z Runtime_error_ 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 16 ms 14684 KB 
//IOI 2011 Day 1 Problem 1 Garden
// First 2 subtask solution 69 points

#include "garden.h"//for CMS
#include "gardenlib.h"//for CMS

//#include "grader.h" // for Yandex

#include <bits/stdc++.h>
#define ll long long
using namespace std;


const int inf=3e5+9,lg=32,MX=1e9+9;
int GoalNode,n;
int nxt[inf],sparse[inf][lg],dis[inf][2],Cycle[2];
vector<pair<int,int> > v[inf];
vector<int> ReversedGraph[inf];

void dfs(int u,int d, bool round){

    dis[u][round]=d;
    for(auto v:ReversedGraph[u]){
        if(v == GoalNode || v == GoalNode+n ){
            Cycle[round]=d+1;
            return ;
        }
        dfs(v,d+1,round);
    }
}

int Queries(int k ){

    for(int i=1;i<=n+n;i++)
        dis[i][0]=dis[i][1]=MX;
    Cycle[0]=Cycle[1]=0;

    dfs(GoalNode , 0 ,0 );
    dfs(GoalNode+n,0,1);
    int ret=0;
    for(int i=1;i<=n;i++)
        if( i != GoalNode)
            if( dis[i][0] ==k || dis[i][1] == k || ( Cycle[0] && ( (k - dis[i][0])%Cycle[0]==0 ) ) || ( Cycle[1] && ( (k - dis[i][1])%Cycle[1]==0 ) ) )
                ret++;

    return ret;
}

int mn(int node){
    pair<int,int> ret=make_pair(1e9,1e9);
    for(auto o:v[node])
        ret=min(ret,o);
    return ret.second;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{

    GoalNode=++P;
    n=N;
    int ans=0;
    for(int i=0;i<M;i++)
        R[i][0]++,R[i][1]++,
        v[R[i][0]].push_back(make_pair(i,R[i][1])),
        v[R[i][1]].push_back(make_pair(i,R[i][0]) );

    for(int i=1;i<=N;i++){
        pair<int,int> temp[3];
        temp[0]=temp[1]=temp[2]=make_pair(1e9,1e9);
        //nxt[i] denotes the nxt node if we start from i or we didn't come to i from the most beautiful trial(adjacent to i)
        // nxt[i+N] denotes the nxt node if we come to i from the most beautiful trail(adjacent to i)

        for(auto o:v[i])
            temp[2]=o,sort(temp,temp+3);

        nxt[i]=temp[0].second+(N*(mn(temp[0].second)==i  ) );
        nxt[i+N]=(temp[1].second<1e9?temp[1].second+(N*(mn(temp[1].second)==i  ) ):temp[0].second+(N*(mn(temp[0].second)==i  ) )  );

    }

    for(int i=1;i<=n+n;i++)
        ReversedGraph[nxt[i]].push_back(i);

    for(int i=0;i<Q;i++)
        answer( Queries(G[i]) );
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:61:9: warning: unused variable 'ans' [-Wunused-variable]
     int ans=0;
         ^~~

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 14684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 14684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 14684 KB Output isn't correct
2 Halted 0 ms 0 KB -