Submission #1349748

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


int bridges_dfs(int now, int back, vector<vector<pair<int,int> > > &way,
                vector<int> &visited, vector<int> &sum, vector<bool> &bridges_flag){
  int res_sum = 0;
  
  visited[now] = 1;
  
  for(int i=0;i<way[now].size();i++){
    if(way[now][i].first == back) continue;

    if(visited[way[now][i].first] == 1){
      sum[way[now][i].first]--;
      sum[now]++;
      bridges_flag[way[now][i].second] = false;
    }else if(visited[way[now][i].first] == 0){
      int res = bridges_dfs(way[now][i].first, now, way, visited, sum, bridges_flag);
      res_sum += res;
      if(res > 0){
        bridges_flag[way[now][i].second] = false;
      }
    }
  }

  visited[now] = 2;
  return res_sum + sum[now];
}

vector<bool> bridges(int n, vector<pair<int,int> > path){ //無向辺
  vector<vector<pair<int,int> > >  way(n, vector<pair<int,int> >());
  vector<int> visited(n,0);
  vector<int> sum(n,0);
  vector<bool> bridges_flag(path.size(), true);

  for(int i=0;i<path.size();i++){
    way[path[i].first].push_back({path[i].second,i});
    way[path[i].second].push_back({path[i].first,i});
  }

  bridges_dfs(0, -1, way, visited, sum, bridges_flag);

  return bridges_flag;
}

/* UnionFind */

struct UnionFind{
  vector<int> data, tree_size;
  UnionFind(int s):data(s,-1),tree_size(s,1) {}
  
  int root(int x){
    if(data[x]==-1) return x;
    return data[x]=root(data[x]);
  }
  
  bool set(int x,int y){
    x=root(x);
    y=root(y);
    if(x==y) return false;
    data[y]=x;
    tree_size[x] += tree_size[y];
    tree_size[y] = 0;
    return true;
  }
  
  bool check(int x,int y){
    x=root(x);
    y=root(y);
    return x==y;
  }
  
  int size(int x){
    return tree_size[root(x)];
  }
  
};

/*Lowest Common Ancstor*/

struct LCA{
  vector<vector<int> > parent;
  vector<int> depth;
  int max_log;
  
  void dfs(vector<vector<int> > &tree,int now,int p,int d){
    parent[0][now] = p;
    depth[now] = d;
    
    for(int i=0;i<tree[now].size();i++){
      if(tree[now][i] != p)
        dfs(tree,tree[now][i],now,d+1);
    }
  }
  
  void init(vector<vector<int> > &tree,int n,int root){
    max_log = 0;
    
    for(int i=1;i<=n*2;i*=2){
      parent.push_back(vector<int>(n,-1));
      max_log++;
    }
    depth.assign(n,-1);
    
    dfs(tree,root,-1,0);
    
    for(int i=0;i<max_log-1;i++){
      for(int j=0;j<n;j++){
        if(parent[i][j]==-1)
          parent[i+1][j] = -1;
        else
          parent[i+1][j] = parent[i][parent[i][j]];
      }
    }
  }
  
  int query(int a,int b){
    if(depth[a] > depth[b]) swap(a,b);
    
    for(int i=0;i<max_log;i++){
      if((depth[b]-depth[a]) >> i & 1){
        b = parent[i][b];
      }
    }
    
    if(a==b) return a;
    
    for(int i=max_log-1;i>=0;i--){
      if(parent[i][a]!=parent[i][b]){
        a = parent[i][a];
        b = parent[i][b];
      }
    }
    
    return parent[0][a];
  }
  
};



int main(){
  int n,m,a,b;
  vector<pair<int,int> > way;

  scanf("%d%d",&n,&m);

  for(int i=0;i<m;i++){
    scanf("%d%d",&a,&b);
    a--; b--;
    way.push_back({a,b});
  }

  auto bridges_flag = bridges(n, way);
  UnionFind uf(n);
  vector<vector<int> > way2(n,vector<int>());
  int v = n;
  
  for(int i=0;i<m;i++){
    if(bridges_flag[i] == false){
      v -= uf.set(way[i].first, way[i].second);
    }
  }

  int root[SIZE];

  for(int i=0;i<n;i++) root[i] = uf.root(i);
  
  for(int i=0;i<m;i++){
    
    if(bridges_flag[i]){
      way2[root[way[i].first]].push_back(root[way[i].second]);
      way2[root[way[i].second]].push_back(root[way[i].first]);
    }
  }

  LCA lca;
  
  lca.init(way2, n, root[0]);

  int q;
  
  scanf("%d",&q);

  for(int i=0;i<q;i++){
    int a, b, c;

    scanf("%d%d%d",&a,&b,&c);
    a = root[a-1];
    b = root[b-1];
    c = root[c-1];

    int t = lca.query(a,c);
    
    if((lca.query(a,b) == b ||
       lca.query(c,b) == b) &&
       lca.depth[t] <= lca.depth[b]){
      puts("OK");
    }else{
      puts("NG");
    }
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:174:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&m);
                      ^
./Main.cpp:177:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&a,&b);
                        ^
./Main.cpp:211:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
                 ^
./Main.cpp:216:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&a,&b,&c);
                             ^

Judge Result