| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 364458 | Sparky_09 | 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 "bits/stdc++.h"
using namespace std;
#define f first
#define s second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
void usaco(string s){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
/*
void dfs(int i, int dist){
//cerr<<"here";
//cerr << "vis " << i << ' ' << dist << '\n';
if(vis[i]){
//found cycle in this dfs
if(i == p){
iscycle = 1;
cycsz = dist; //dist from p or p+n
}
return;
}
vis[i] = 1;
if(i == p or i == p+n){ //todo make P and N global(done)
iscycle = 0; // set to nocycle so if we find one in this dfs we know rest of nodes are in cycle too
}
for(int x: rgraph[i]){
//cerr << i << " goes to " << x << '\n';
if(x < n){
verindfs[x] = 1;
distt[x] = dist;
}
dfs(x, dist+1);
}
}
*/
int N,M,P;
int x[150010],y[150010];
vector<pair<int,int>> adj[150010];
vector<int> adj2[2 * 150010];
int dis[2 * 150010][2],sz[2];
int small[2 * 150010];
void dfs(int node, int source, bool b){
for(int x:adj2[node]){
if(x == source){
sz[b] = dis[node][b]+1;
continue;
}
if(dis[x][b] == 0){
dis[x][b] = dis[node][b]+1;
dfs(x,source,b);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
/*
for(int i=0;i<n;i++){
//cerr<<i<<' '<<adj[i].sz()<<'\n';
//from i we go to min
//from i+n we go to second min
//we go to j if it isnt min of j
//otherwise we go to j+n
int go = adj[i][0].second;
//cerr << "aa" << i << ' ' << go << '\n';
if(adj[i][0].first == adj[go][0].first){
//we go to j+n
//graph[i].push_back(go + n);
rgraph[go + n].push_back(i);
}
else{
//we can go to j
//graph[i].push_back(go);
rgraph[go].push_back(i);
}
//now we have to consider the case for i+n too;
if(adj[i].sz() > 1){
int go2 = adj[i][1].second;
//we are not at i+n and we can only go thru min2
//which is adj[i][1].first
//cerr << "bb" << i << ' ' << go2 << '\n';
if(adj[i][1].first == adj[go2][0].first){
//i forgot what i was doing
//we are going to j if min2 is not min of j so it can only go to its min2
//makes sense
//graph[i+n].push_back(go2 + n);
rgraph[go2 + n].push_back(i + n);
}
else{
//graph[i+n].push_back(go2);
rgraph[go2].push_back(i + n);
}
}
else{
//it doesnt have 2nd min to go to
//so it will have to go through min again
//so same as old case?
int go3 = adj[i][0].second;
if(adj[i][0].first == adj[go3][0].first){
//we go to j+n
//graph[i+n].push_back(go3 + n);
rgraph[go3 + n].push_back(i + n);
}
else{
//we can go to j
//graph[i+n].push_back(go3);
rgraph[go3].push_back(i+n);
}
}
}
*/
for(int i=0;i<M;i++){
x[i]=R[i][0];
y[i]=R[i][1];
adj[x[i]].push_back({i,y[i]});
adj[y[i]].push_back({i,x[i]});
}
for(int i=0;i<N;i++){
sort(adj[i].begin(),adj[i].end());
small[i]=adj[i][0].first;
}
for(int i=0;i<N;i++){
if((int)adj[i].sz()==1){
adj2[adj[i][0].s+N*(adj[i][0].f==small[adj[i][0].s])].push_back(i);
adj2[adj[i][0].s+N*(adj[i][0].f==small[adj[i][0].s])].push_back(i+N);
}
else{
adj2[adj[i][0].s+N*(adj[i][0].f==small[adj[i][0].s])].push_back(i);
adj2[adj[i][1].s+N*(adj[i][1].f==small[adj[i][1].s])].push_back(i+N);
}
}
dfs(P,P,0);
dfs(P+N,P+N,1);
for(int i=0;i<Q;i++){
int K=G[i];
int ans=0;
for (int j=0;j<N;j++){
bool good=false;
for (int k=0;k<2;k++){
if(dis[j][k]!=0){
if (sz[k]==0){
if (dis[j][k]==K)
good=true;
}
else{
if(K-dis[j][k]>=0 && sz[k]!=0 && (K-dis[j][k])%sz[k]==0)
good=true;
}
}
else if(j==P && sz[k]!=0 && K%sz[k]==0)
good=true;
}
ans+=good;
}
answer(ans);
}
}
//new graph is made should work ok
//now we need to reverse the edges
//why not just change the graph to make it go in reverse
//why will this work
//i start dfs from p and see what all i can visit at k dist
//if p is in a cycle then we check cycle sz and then dist to other nodes
//total dist is distoutsidecyc + (numberofcyclesdone * szofcycle)
//numberofcycles done is int then path is valid
//how to check the other nodes we visited are part of cycle too?
//launch dfs we ca have some temp bool iscycle or smthn
//i made rgraph which we will traverse from p and p+n
//now the dfs
//we dont need iscycle? since each node now has outdegree 1 always
//so if theres a cycle all nodes visited are part of it