oj.uz

Submission #364460

# Submission time Handle Problem Language Result Execution time Memory
364460 2021-02-09T08:48:38 Z Sparky_09 Tropical Garden (IOI11_garden) C++14
100 / 100
 2812 ms 44012 KB 
#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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11116 KB Output is correct
2 Correct 8 ms 11116 KB Output is correct
3 Correct 8 ms 11116 KB Output is correct
4 Correct 9 ms 10988 KB Output is correct
5 Correct 8 ms 10988 KB Output is correct
6 Correct 9 ms 11244 KB Output is correct
7 Correct 10 ms 10988 KB Output is correct
8 Correct 9 ms 10988 KB Output is correct
9 Correct 13 ms 11372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11116 KB Output is correct
2 Correct 8 ms 11116 KB Output is correct
3 Correct 8 ms 11116 KB Output is correct
4 Correct 9 ms 10988 KB Output is correct
5 Correct 8 ms 10988 KB Output is correct
6 Correct 9 ms 11244 KB Output is correct
7 Correct 10 ms 10988 KB Output is correct
8 Correct 9 ms 10988 KB Output is correct
9 Correct 13 ms 11372 KB Output is correct
10 Correct 8 ms 10988 KB Output is correct
11 Correct 21 ms 13676 KB Output is correct
12 Correct 39 ms 15980 KB Output is correct
13 Correct 70 ms 36204 KB Output is correct
14 Correct 161 ms 27060 KB Output is correct
15 Correct 189 ms 27628 KB Output is correct
16 Correct 134 ms 24320 KB Output is correct
17 Correct 122 ms 23020 KB Output is correct
18 Correct 38 ms 16108 KB Output is correct
19 Correct 151 ms 27116 KB Output is correct
20 Correct 179 ms 27628 KB Output is correct
21 Correct 135 ms 24044 KB Output is correct
22 Correct 120 ms 23020 KB Output is correct
23 Correct 151 ms 28396 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11116 KB Output is correct
2 Correct 8 ms 11116 KB Output is correct
3 Correct 8 ms 11116 KB Output is correct
4 Correct 9 ms 10988 KB Output is correct
5 Correct 8 ms 10988 KB Output is correct
6 Correct 9 ms 11244 KB Output is correct
7 Correct 10 ms 10988 KB Output is correct
8 Correct 9 ms 10988 KB Output is correct
9 Correct 13 ms 11372 KB Output is correct
10 Correct 8 ms 10988 KB Output is correct
11 Correct 21 ms 13676 KB Output is correct
12 Correct 39 ms 15980 KB Output is correct
13 Correct 70 ms 36204 KB Output is correct
14 Correct 161 ms 27060 KB Output is correct
15 Correct 189 ms 27628 KB Output is correct
16 Correct 134 ms 24320 KB Output is correct
17 Correct 122 ms 23020 KB Output is correct
18 Correct 38 ms 16108 KB Output is correct
19 Correct 151 ms 27116 KB Output is correct
20 Correct 179 ms 27628 KB Output is correct
21 Correct 135 ms 24044 KB Output is correct
22 Correct 120 ms 23020 KB Output is correct
23 Correct 151 ms 28396 KB Output is correct
24 Correct 9 ms 10988 KB Output is correct
25 Correct 185 ms 13676 KB Output is correct
26 Correct 279 ms 15980 KB Output is correct
27 Correct 2529 ms 36332 KB Output is correct
28 Correct 1462 ms 27244 KB Output is correct
29 Correct 2797 ms 27884 KB Output is correct
30 Correct 1662 ms 24556 KB Output is correct
31 Correct 1596 ms 23276 KB Output is correct
32 Correct 295 ms 16236 KB Output is correct
33 Correct 1466 ms 27360 KB Output is correct
34 Correct 2812 ms 27884 KB Output is correct
35 Correct 1763 ms 24176 KB Output is correct
36 Correct 1623 ms 23064 KB Output is correct
37 Correct 1350 ms 28780 KB Output is correct
38 Correct 2672 ms 44012 KB Output is correct