| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 416095 | dreezy | Tropical Garden (IOI11_garden) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
/*****************************************/
//just have to implement
#define pi pair<int,int>
#define pb push_back
#define ll long long
#define f first
#define s second
const int maxn = 35e5 + 5;
const int maxlogn = 30;
//int level[maxn];
int graph[maxn];
int up[maxn][maxlogn];
bool follow_path(int n,int p, int k){
//cout << n <<": ";
int cur = n*2;
for(int i =0; i<k; i++){
cur = graph[cur];
}
//cout << n <<", "<< p<<", "<<k<<endl;
if(cur/2 == p) return 1;
return 0;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
memset(graph, -1, sizeof(graph));
for(int i =0; i<M; i++){
int a = 2* R[i][0];
int b = 2* R[i][1];
if(graph[a] == -1){
if( graph[b] == -1){
graph[a] = b+1;
graph[a+1] = b+1;
}
else{
graph[a] = b;
graph[a+1] = b;
}
}
else if(graph[a] == graph[a+1]){
if(graph[b] == -1)
graph[a+1] = b+1;
}
if(graph[b] == -1){
if(graph[a] == b +1){
graph[b] = a+1;
graph[b+1] = a+1;
}
else{
graph[b] = a;
graph[b+1]= a;
}
}
else if(graph[b] == graph[b+1]){
if(graph[a] == b)
graph[b+1] = a+1;
graph[b+1] = a;
}
}
/*
for(int i =0; i< N; i++){
int a = graph[i*2];
int b= graph[i*2 +1];
if(a % 2== 1){
cout << i <<" -> "<<a/2<<"'\n";
}
else{
cout << i <<" -> "<<a/2<<"\n";
}
if(b % 2== 1){
cout << i <<"' -> "<<b/2<<"'\n";
}
else{
cout << i <<"' -> "<<b/2<<"\n";
}
}
*/
for(int i =0; i<Q; i++){
ll ans = 0;
for(int j =0; j<N; j++){
ans+=follow_path(j,P, G[i]);
}
answer(ans);
}
}
/******************************************/
#define MAX_M 1000000
#define MAX_Q 2000
static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&M,&P));
for(i=0; i<M; i++)
my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
my_assert(1==scanf("%d",&Q));
for(i=0; i<Q; i++)
my_assert(1==scanf("%d",&G[i]));
for(i=0; i<Q; i++)
my_assert(1==scanf("%d",&solutions[i]));
}
void answer(int x)
{
if(answer_count>=Q) {
printf("Incorrect. Too many answers.\n");
exit(0);
}
answers[answer_count] = x;
answer_count++;
}
int main()
{
freopen("grader.in.1","r",stdin);
int correct, i;
read_input();
answer_count = 0;
count_routes(N,M,P,R,Q,G);
if(answer_count!=Q) {
printf("Incorrect. Too few answers.\n");
exit(0);
}
correct = 1;
for(i=0; i<Q; i++)
if(answers[i]!=solutions[i])
correct = 0;
if(correct)
printf("Correct.\n");
else {
printf("Incorrect.\n");
printf("Expected: ");
for(i=0; i<Q; i++)
printf("%d ",solutions[i]);
printf("\nReturned: ");
for(i=0; i<Q; i++)
printf("%d ",answers[i]);
}
return 0;
}