Submission #364460

#	Time	Username	Problem	Language	Result	Execution time	Memory
364460		Sparky_09	Tropical Garden (IOI11_garden)	C++14	100 / 100	2812 ms	44012 KiB

garden

#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].size()==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

Compilation message (stderr)

garden.cpp: In function 'void usaco(std::string)':
garden.cpp:17:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   17 |   freopen((s+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   18 |   freopen((s+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31