oj.uz

답안 #218903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
218903 2020-04-03T05:16:37 Z FieryPhoenix 열대 식물원 (Tropical Garden) (IOI11_garden) C++11
0 / 100
 23 ms 21888 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
#define f first
#define s second

int N,M,P;
int x[150001],y[150001];
vector<pair<int,int>>adj[150001];
vector<int>adj2[300001];
int dis[300001][2],size[2];
int minEdge[300001];

void dfs(int node, int source, bool b){
  for (int x:adj2[node]){
    if (x==source){
      assert(size[b]==0);
      size[b]=dis[node][b]+1;
      return;
    }
    if (dis[x][b]==0){
      dis[x][b]=dis[node][b]+1;
      dfs(x,source,b);
    }
  }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
  for (int i=0;i<M;i++){
    x[i]=R[i][0];
    y[i]=R[i][1];
    adj[x[i]].push_back({i,y[i]});
    adj[y[i]].push_back({i,x[i]});
  }
  for (int i=0;i<N;i++){
    sort(adj[i].begin(),adj[i].end());
    minEdge[i]=adj[i][0].first;
  }
  for (int i=0;i<N;i++){
    if ((int)adj[i].size()==1){
      adj2[adj[i][0].s+N*(adj[i][0].f==minEdge[adj[i][0].s])].push_back(i);
      adj2[adj[i][0].s+N*(adj[i][0].f==minEdge[adj[i][0].s])].push_back(i+N);
    }
    else{
      adj2[adj[i][0].s+N*(adj[i][0].f==minEdge[adj[i][0].s])].push_back(i);
      adj2[adj[i][1].s+N*(adj[i][1].f==minEdge[adj[i][1].s])].push_back(i+N);
    }
  }
  dfs(P,P,0);
  dfs(P+N,P+N,1);
  for (int i=0;i<Q;i++){
    int K=G[i];
    int ans=0;
    for (int j=0;j<N;j++){
      bool good=false;
      for (int k=0;k<2;k++){
	if (dis[j][k]!=0){
	  if (size[k]==0){
	    if (dis[j][k]==K)
	      good=true;
	  }
	  else{
	    if (K-dis[j][k]>=0 && (K-dis[j][k])%size[k]==0)
	      good=true;
	  }
	}
	else if (j==P && K%size[k]==0)
	  good=true;

      }
      ans+=good;
    }
    answer(ans);
  }
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11136 KB Output is correct
2 Correct 11 ms 11136 KB Output is correct
3 Correct 12 ms 11136 KB Output is correct
4 Runtime error 23 ms 21888 KB Execution killed with signal 8 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11136 KB Output is correct
2 Correct 11 ms 11136 KB Output is correct
3 Correct 12 ms 11136 KB Output is correct
4 Runtime error 23 ms 21888 KB Execution killed with signal 8 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11136 KB Output is correct
2 Correct 11 ms 11136 KB Output is correct
3 Correct 12 ms 11136 KB Output is correct
4 Runtime error 23 ms 21888 KB Execution killed with signal 8 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -