| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 29481 | ozaslan | 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<bits/stdc++.h>
#include<vector>
#include<map>
#include<set>
#include<stdio.h>
#include "garden.h"
#include "gardenlib.h"
#define MAX_N 100005
#define mp make_pair
#define pb push_back
#define oo (1<<28)
using namespace std;
/*
#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.2", "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;
}*/
vector< pair<int, int> > E[MAX_N];
vector< pair<int, int> > donus[MAX_N][2];
map< pair<int, int>, pair<int, int> >::iterator mapit;
int kul[MAX_N][2], dongu1, dongu2;
int uzak1[MAX_N], uzak2[MAX_N], gec1[MAX_N], gec2[MAX_N];
void sudoDFS(int dugum, int ata, int ataNo) {
int enGuzel = E[dugum][0].second;
int enGuzel2 = E[dugum].size() == 1 ? E[dugum][0].second : E[dugum][1].second;
if (enGuzel == ata) {
donus[dugum][1].pb( mp(ata, ataNo) );
if (kul[dugum][1]) return;
kul[dugum][1] = 1;
sudoDFS(enGuzel2, dugum, 1);
}
else {
donus[dugum][0].pb( mp(ata, ataNo) );
if (kul[dugum][0]) return;
kul[dugum][0] = 1;
sudoDFS(enGuzel, dugum, 0);
}
}
void sudoTreeOlustur(int N) {
for(int i = 0; i < N; i++) {
int enGuzel = oo, dugum;
if(kul[i][0]) continue;
kul[i][0] = 1;
sudoDFS(E[i][0].second, i, 0);
}
}
void tersDFS1(int dugum, int dugumNo, int derinlik) {
if (dugumNo == 0) uzak1[dugum] = derinlik;
kul[dugum][dugumNo] = 1;
gec1[dugum] = 1;
for(int i = 0; i < donus[dugum][dugumNo].size(); i++) {
int v = donus[dugum][dugumNo][i].first, m = donus[dugum][dugumNo][i].second;
if (kul[v][m]) {
dongu1 = derinlik +1;
continue;
}
tersDFS1(v, m, derinlik+1);
}
}
void tersDFS2(int dugum, int dugumNo, int derinlik) {
if(dugumNo == 0) uzak2[dugum] = derinlik;
kul[dugum][dugumNo] = 1;
gec2[dugum] = 1;
for(int i = 0; i < donus[dugum][dugumNo].size(); i++) {
int v = donus[dugum][dugumNo][i].first, m = donus[dugum][dugumNo][i].second;
if (kul[v][m] ) {
dongu2 = derinlik +1;
continue;
}
tersDFS2(v, m, derinlik+1);
}
}
void uzaklikBul(int P) {
int sonuc = 0;
memset(kul, 0, sizeof kul);
tersDFS1( P, 0, 0);
memset(kul, 0, sizeof kul);
tersDFS2( P, 1, 0);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for (int i = 0; i < M; i++) {
E[ R[i][0] ].push_back( make_pair(i, R[i][1]) );
E[ R[i][1] ].push_back( make_pair(i, R[i][0]) );
}
sudoTreeOlustur(N);
uzaklikBul(P);
int sonuc;
for (int i = 0; i < Q; i++) {
sonuc = 0;
for(int j = 0; j < N; j++) {
if(gec1[j] && uzak1[j] <= G[i]) {
if(dongu1 && uzak1[j] % dongu1 == G[j] % dongu1) sonuc++;
else if(G[i] == uzak1[j]) sonuc++;
}
if(gec2[j] && uzak2[j] <= G[i]) {
if(dongu2 && uzak2[j] % dongu2 == G[j] % dongu2) sonuc++;
else if(G[i] == uzak2[j]) sonuc++;
}
}
answer(sonuc);
}
}
/*for(int i=0; i<MAX_N; i++)
if(uzak1[i]) printf("%d %d\n", i, uzak1[i]);
printf("\n");
for(int i=0; i<MAX_N; i++)
if(uzak2[i]) printf("%d %d\n", i, uzak2[i]);
*/
/* for (mapit = sudoTree.begin(); mapit != sudoTree.end(); ++mapit) {
printf("%d-%d -> %d-%d\n", mapit->first.first, mapit->first.second, mapit->second.first, mapit->second.second);
}
for (mapvit = donus.begin(); mapvit != donus.end(); ++mapvit) {
printf("\n%d-%d -> ", mapvit->first.first, mapvit->first.second);
for(int i=0; i< mapvit->second.size(); i++)
printf("%d-%d ", mapvit->second[i].first, mapvit->second[i].second);
*/