Submission #24131938

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef pair<string,string> Pstring;
typedef pair<double,double> Pdouble;


#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define Precision13 cout << fixed << setprecision(13)
const double PI=3.14159265358979323846;
const int MAX = 510000;
const int MOD = 1000000007;
const int INF = 1<<29;
using Graph = vector<vector<ll>>;



int main() {
    // 頂点数と辺数、s と t
    int N, q, s, t;
    cin >> N >> q;

    // グラフ入力受取
    Graph G(N+1);
    for (int i = 0; i < N-1; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    vector<int> dist(N+1, -1);
    queue<int> que;

    s = 1;

    dist[s] = 0, que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
            if (dist[nv] == -1) {
                dist[nv] = dist[v] + 1;
                que.push(nv);
            }
        }
    }

    for (int i = 0; i < q; ++i) {
      cin >> s >> t;
      if((dist[s]-dist[t])%2 == 0){
        cout << "Town" << endl;
      }else{
        cout << "Road" << endl;
      }
    }
      
}

Submission Info

Judge Result