//#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;
}*/
//int N;
vector< pair<int, int> > E[MAX_N];
//map< pair<int, int>, pair<int, int> > sudoTree;
map< pair<int, int>, vector< pair<int, int> > > donus;
map< pair<int, int>, pair<int, int> >::iterator mapit;
map< pair<int, int>, vector< pair<int, int> > >::iterator mapvit;
set< pair<int, int> > kul;
void sudoDFS(int dugum, int gelenYol, int ata, int ataNo) {
// printf("Dugum: %d, gelenYol: %d, ata:%d, ataNo:%d, ", dugum, gelenYol, ata, ataNo);
int enGuzel = oo, dugum1;
int enGuzel2 = oo, dugum2;
for(int i = 0; i < E[dugum].size(); i++) {
int yol = E[dugum][i].first;
if(yol < enGuzel) {
enGuzel2 = enGuzel;
dugum2 = dugum1;
enGuzel = yol;
dugum1 = E[dugum][i].second;
}
else if(yol < enGuzel2) {
enGuzel2 = yol;
dugum2 = E[dugum][i].second;
}
}
// printf("enGuzel: %d\n", enGuzel);
if (enGuzel == gelenYol) {
// sudoTree[ mp(ata, ataNo) ] = mp(dugum, 1);
donus[ mp(dugum, 1) ].pb( mp(ata, ataNo) );
if (kul.count( mp(dugum, 1) ) ) return;
kul.insert( mp(dugum, 1) );
if (enGuzel2 != oo) sudoDFS(dugum2, enGuzel2, dugum, 1);
else sudoDFS(ata, gelenYol, dugum, 1);
}
else {
// sudoTree[ mp(ata, ataNo) ] = mp(dugum, 0);
donus[ mp(dugum, 0) ].pb( mp(ata, ataNo) );
if (kul.count( mp(dugum, 0) ) ) return;
kul.insert( mp(dugum, 0) );
sudoDFS(dugum1, enGuzel, dugum, 0);
}
}
void sudoTreeOlustur(int N) {
for(int i = 0; i < N; i++) {
int enGuzel = oo, dugum;
if(!kul.count(mp(i, 0) ) ) {
for (int j = 0; j < E[i].size(); j++) {
int yol = E[i][j].first;
if (yol < enGuzel) {
enGuzel = yol;
dugum = E[i][j].second;
}
}
kul.insert( mp(i, 0) );
sudoDFS(dugum, enGuzel, i, 0);
}
}
/* 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);
*/
}
int uzak1[MAX_N], uzak2[MAX_N], dongu1, dongu2;
void tersDFS1(pair<int, int> dugum, int derinlik) {
// printf("%d-%d %d\n", dugum.first, dugum.second, derinlik);
if (dugum.second == 0) uzak1[derinlik]++;
kul.insert(dugum);
for(int i = 0; i < donus[dugum].size(); i++) {
if (kul.count(donus[dugum][i]) ) {
dongu1 = derinlik +1;
continue;
}
tersDFS1(donus[dugum][i], derinlik+1);
}
// printf("Deneme\n");
}
void tersDFS2(pair<int, int> dugum, int derinlik) {
// printf("%d-%d %d\n", dugum.first, dugum.second, derinlik);
if(dugum.second == 0) uzak2[derinlik]++;
kul.insert(dugum);
for(int i = 0; i < donus[dugum].size(); i++) {
if (kul.count(donus[dugum][i]) ) {
dongu2 = derinlik +1;
continue;
}
tersDFS2(donus[dugum][i], derinlik+1);
}
// printf("Deneme\n");
}
void uzaklikBul(int P) {
int sonuc = 0;
kul.clear();
if (donus.count( mp(P, 0) ) ) tersDFS1( mp(P, 0), 0);
kul.clear();
if (donus.count( mp(P, 1) ) ) tersDFS2( mp(P, 1), 0);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
//N = n;
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);
/*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]);
*/
int sonuc;
for (int i = 0; i < Q; i++) {
sonuc = 0;
if (dongu1) sonuc += uzak1[ G[i] % dongu1];
else sonuc += uzak1[ G[i] ];
if (dongu2) sonuc += uzak2[ G[i] % dongu2];
else sonuc += uzak2[ G[i] ];
answer(sonuc);
}
}
Compilation message
garden.cpp: In function 'void sudoDFS(int, int, int, int)':
garden.cpp:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < E[dugum].size(); i++) {
~~^~~~~~~~~~~~~~~~~
garden.cpp: In function 'void sudoTreeOlustur(int)':
garden.cpp:143:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < E[i].size(); j++) {
~~^~~~~~~~~~~~~
garden.cpp: In function 'void tersDFS1(std::pair<int, int>, int)':
garden.cpp:176:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < donus[dugum].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void tersDFS2(std::pair<int, int>, int)':
garden.cpp:192:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < donus[dugum].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void uzaklikBul(int)':
garden.cpp:205:7: warning: unused variable 'sonuc' [-Wunused-variable]
int sonuc = 0;
^~~~~
garden.cpp: In function 'void sudoDFS(int, int, int, int)':
garden.cpp:132:12: warning: 'dugum1' may be used uninitialized in this function [-Wmaybe-uninitialized]
sudoDFS(dugum1, enGuzel, dugum, 0);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void sudoTreeOlustur(int)':
garden.cpp:153:14: warning: 'dugum' may be used uninitialized in this function [-Wmaybe-uninitialized]
sudoDFS(dugum, enGuzel, i, 0);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
