Submission #1104574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104574		spycoderyt	Tropical Garden (IOI11_garden)	C++17	0 / 100	3 ms	16976 KiB

garden

#include <bits/stdc++.h>
#define s second
#define f first
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int N = 3e5+5;
int K,P,ans=0;
vector<pair<int,int> > A[N];
vector<int> B[N];
int vis[N],dis[N];
int len=0;
int n;
void dfs(int u, int k) {
    // cout << u << "\n";
    dis[u]=k;
    for(auto nxt : B[u]) {
        // cout << nxt << "\n";
        if(nxt == P){
            len = k;
            continue;
        }
        else if (vis[nxt]) continue;
        vis[nxt]=1;
        dfs(nxt,k+1);
        vis[nxt]=0;
    }
}
void count_routes(int nn, int m, int pp, int R[][2], int Q, int queries[])
{
    n = nn;
    P = pp;
    for(int i = 0;i<2*n;i++)dis[i] = 1e9;
    for(int i = 0;i<m;i++) {
        A[R[i][0]].push_back({i,R[i][1]});
        A[R[i][1]].push_back({i,R[i][0]});
    }
    for(int i = 0;i<n;i++) sort(A[i].begin(),A[i].end());
    // i is reached from other edge, i+n is reached from best edge
    for(int i = 0;i<n;i++) {
        int nxt = A[i][0].s;
        if(i == A[nxt][0].s) B[nxt+n].push_back(i);// cout << i << " " << nxt+n<<"\n";
        else B[nxt].push_back(i);//cout << i << " " << nxt<<"\n";
        // i to A[i][0].f
    }
    for(int i = 0;i<n;i++) {
        // i+n to A[i][1].f
        if(A[i].size() >= 2) {
            int nxt = A[i][1].s;
            if(i == A[nxt][0].s) B[nxt+n].push_back(i+n);//cout << i+n << " " << nxt+n<<"\n";
            else B[nxt].push_back(i+n);//cout << i+n << " " << nxt<<"\n";
        } else {
            int nxt = A[i][0].s;
            if(i == A[nxt][0].s) B[nxt+n].push_back(i+n);//cout << i+n << " " << nxt+n<<"\n";
            else B[nxt].push_back(i+n);//cout << i+n << " " << nxt<<"\n";
        }
    }
    // dfs from pp
    vis[P]=1;
    dfs(P,1);
    vis[P]=0;
    P+=n;

    // dfs from pp
    vis[P]=1;
    dfs(P,1);
    vis[P]=0;
    // cout << "len " << len << "\n";
    // for(int i = 0;i<n;i++)cout<<dis[i]<< " ";
    // cout << "\n";
    for(int j = 0;j<Q;j++) {
        ans=0;
        int tar = queries[j];
        if(len==0) {
            for(int i = 0;i<n;i++) if(dis[i] != 1e9 && dis[i]==tar) ans++;
            answer(ans);
        } else {
            for(int i = 0;i<n;i++) if(dis[i] != 1e9 && dis[i]%len == tar) ans++;
            answer(ans);
        }
    }
}


/*


/usr/bin/g++ -DEVAL -std=gnu++11 -O2 -pipe -s -o garden2 grader.cpp garden2.cpp
./garden2 

6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
2


5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
1 2



*/

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