| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 354395 | AmirElarbi | 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 <iostream>
#include <vector>
#include <algorithm>
#define MAX_M 150002
#define optimize_io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
int n, m, p;
int q, k;
int best[MAX_M];
int edges[MAX_M][2];
vector <int> E[MAX_M];
vector < pair <int, int> > out[MAX_M][2];
bool vis[MAX_M][2];
void createNewGraph( int node, int w ){
if( vis[node][w] )
return;
vis[node][w] = 1;
int nnode, nw;
if( w == 1 )
nnode = E[node].size() > 1 ? E[node][1] : E[node][0];
else
nnode = best[node];
if( best[nnode] == node )
nw = 1;
else
nw = 0;
createNewGraph( nnode, nw );
out[nnode][nw].push_back( make_pair( node, w ) );
}
int D[MAX_M][2][2], lenght[2] = { 1000000001, 1000000001 };
int visited[MAX_M][2], color;
void DFS( int node, int w, int d, int s ){
if( visited[node][w] == color ){
if( node == p && w == s )
lenght[s] = d;
return;
}
visited[node][w] = color;
D[node][w][s] = d;
for( int i = 0; i < out[node][w].size(); i++ )
DFS( out[node][w][i].first, out[node][w][i].second, d + 1, s );
}
int main(){
optimize_io
cin >> n >> m >> p;
for( int i = 0; i < n; i++ )
best[i] = -1;
for( int i = 1; i <= m; i++ ){
cin >> edges[i][0] >> edges[i][1];
E[ edges[i][0] ].push_back( edges[i][1] );
E[ edges[i][1] ].push_back( edges[i][0] );
if( best[ edges[i][0] ] == -1 )
best[ edges[i][0] ] = edges[i][1];
if( best[ edges[i][1] ] == -1 )
best[ edges[i][1] ] = edges[i][0];
}
for( int i = 0; i < n; i++ )
for( int j = 0; j < 2; j++ )
if( !vis[i][j] )
createNewGraph( i, j );
for( int i = 0; i < n; i++ )
for( int j = 0; j < 2; j++ )
for( int k = 0; k < 2; k++ )
D[i][j][k] = 1000000001;
color++;
DFS( p, 0, 0, 0 );
color++;
DFS( p, 1, 0, 1 );
cin >> q;
int res;
for( int i = 1; i <= q; i++ ){
cin >> k;
res = 0;
for( int j = 0; j < n; j++ ){
if( k >= D[j][0][0] )
res += ( ( k - D[j][0][0] ) % lenght[0] ) == 0 ? 1 : 0;
if( k >= D[j][0][1] )
res += ( ( k - D[j][0][1] ) % lenght[1] ) == 0 ? 1 : 0;
}
cout << res ;
if( i < q )
cout << " ";
else
cout << "\n";
}
return 0;
}