| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 543424 | ogibogi2004 | Tropical Garden (IOI11_garden) | C++14 | 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 "garden.h"
#include "gardenlib.h"
#include <stdio.h>
#include <stdlib.h>
#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++;
}
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=15e4+6;
const int INF=1e9;
bool ending[2*MAXN];
int nxt[2*MAXN];
vector<pair<int,int> >edges;
vector<pair<int,int> >g[MAXN];
int dist[2*MAXN];
int which[2*MAXN];
vector<int>rev[MAXN];
int cnt[3*MAXN];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for(int i=0;i<M;i++)
{
R[i][0]++;
R[i][1]++;
}
//for(int i=0;i<Q;i++)G[i]++;
P++;
for(int i=0;i<M;i++)
{
if(R[i][1]==P)
{
//cout<<" - "<<2*i<<endl;
ending[2*i]=1;
}
edges.push_back({R[i][0],R[i][1]});
if(R[i][0]==P)
{
//cout<<" - "<<2*i+1<<endl;
ending[2*i+1]=1;
}
edges.push_back({R[i][1],R[i][0]});
g[R[i][0]].push_back({R[i][1],2*i});
g[R[i][1]].push_back({R[i][0],2*i+1});
}
for(int i=0;i<edges.size();i++)
{
if(g[edges[i].second].size()==1)
{
nxt[i]=g[edges[i].second][0].second;
}
else if(g[edges[i].second][0].first==edges[i].first)
{
nxt[i]=g[edges[i].second][1].second;
}
else
{
nxt[i]=g[edges[i].second][0].second;
}
rev[nxt[i]].push_back(i);
}
queue<int>q;
for(int i=0;i<edges.size();i++)
{
dist[i]=INF;
if(ending[i]==1)
{
//cout<<" "<<i<<endl;
q.push(i);
dist[i]=1;
which[i]=i;
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(auto xd:rev[u])
{
if(dist[xd]!=INF)continue;
dist[xd]=dist[u]+1;
which[xd]=which[u];
q.push(xd);
}
}
int cycle_size=-1;
for(int i=0;i<edges.size();i++)
{
if(dist[i]==1)
{
//cout<<edges[i].first<<" "<<edges[i].second<<" "<<dist[i]<<endl;
if(dist[nxt[i]]==INF)continue;
cycle_size=dist[nxt[i]]+1;
}
}
for(int i=1;i<=N;i++)
{
int e=g[i][0].second;
if(dist[e]!=INF)
{
cnt[dist[e]]++;
}
}
if(cycle_size!=-1)for(int i=cycle_size;i<3*MAXN;i++)cnt[i]+=cnt[i-cycle_size];
for(int i=0;i<Q;i++)
{
if(G[i]<3*MAXN)answer(cnt[G[i]]);
else if(cycle_size==-1)answer(0);
else
{
int k=(G[i]-3*MAXN)/cycle_size+1;
k=G[i]-k*cycle_size;
answer(cnt[k]);
}
}
}
int main()
{
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;
}
/*
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
1 2
*/