#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <bitset>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define mp make_pair
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
const int nmax = 2000001;
vector <vector <pii> > g(nmax);
struct fenwick{
int n;
vector <int> bit;
fenwick(){
n = 0;
}
fenwick(int n) : n(n){
bit.resize(n + 1);
}
void add(int pos, int val){
while(pos <= n){
bit[pos] += val;
pos += (pos & -pos);
}
}
int get(int pos){
int res = 0;
while(pos){
res += bit[pos];
pos -= (pos & -pos);
}
return res;
}
int sum(int l, int r){
return get(r) - get(l - 1);
}
}fen[nmax];
int sz[nmax];
vector <bool> marked(nmax);
void dfs(int v, int e){
sz[v] = 0;
for(auto x : g[v]){
int to = x.f;
if(marked[to] || to == e) continue;
dfs(to, v);
sz[v] += sz[to];
}
sz[v]++;
}
int find_cent(int v, int n, int e){
if(sz[v] * 2 < n) return 0;
for(auto x : g[v]){
int to = x.f;
if(marked[to] || to == e) continue;
int y = find_cent(to, n, v);
if(y) return y;
}
return v;
}
multiset <pii> st[nmax];
vector <vector <pii> > vec(nmax);
vector <vector <pii> > cc(nmax);
int c;
void DFS(int v, int e, int lst, bool inc, bool dc, int ind){
if(inc){
st[c].insert(mp(lst, ind));
vec[v].pb(mp(c, ind));
}
if(dc){
cc[v].pb(mp(c, ind));
}
for(auto x : g[v]){
int to = x.f; int len = x.s;
bool ndc, ninc;
ndc = dc, ninc = inc;
if(marked[to] || to == e) continue;
if(len > lst) ndc = false;
if(len < lst) ninc = false;
DFS(to, v, lst, ninc, ndc, ind);
}
}
void decompose(int v){
dfs(v, v);
int x= find_cent(v, sz[v], v);
st[x].insert({0, 1});
cc[x].pb({x, 1});
vec[x].pb({x, 1e9});
int cur = 2;
c = x;
marked[x] = true;
//cout << x << ' ';
for(auto ed : g[x]){
int to = ed.f;
if(marked[to]) continue;
DFS(to, x, ed.s, true, true, cur);
cur++;
}
st[x].insert({0, cur});
fen[x] = {cur};
for(auto ed : g[x]){
if(!marked[ed.f])
decompose(ed.f);
}
}
bool Query(int a, int b){
for(auto x : vec[a]){
for(auto y : cc[b]){
if(x.f == y.f && x.s != y.s){
if(x.s > y.s) return true;
return false;
}
}
}
return false;
}
vector <int> p(nmax), s(nmax);
void make_set(int v){
p[v] = v;s[v] = 1;
}
int find_set(int v){
return p[v] == v ? v : p[v] = find_set(p[v]);
}
void union_sets(int a, int b){
a = find_set(a); b= find_set(b);
if(s[a] < s[b]) swap(a, b);
p[b] = a;
s[a] += s[b];
}
int Count(int a, int t){
ll ans = 0;
for(auto x : cc[a]){
int v = x.f;
if(find_set(v) != find_set(a)) continue;
while(!st[v].empty()){
int x = st[v].begin()->f;
if(x < t) {
fen[v].add(st[v].begin()->s, 1);
st[v].erase(st[v].begin());
}
else break;
}
ans += fen[v].sum(x.s + 1, fen[v].n);
}
return ans;
}
int main(){
int n; cin >> n;
int m; cin >> m;
vector <pair<char, pii> > query(n + m );
m += n - 1;
for(int i= 1; i <= n; i++){
make_set(i);
}
for(int i = 1; i <= m; i++){
char c; cin >> c;
if(c == 'S'){
int a, b; cin >> a >> b;
g[a].pb({b, i});
g[b].pb({a, i});
query[i] = {c, {a, b}};
}
if(c == 'Q'){
int a, d; cin >> a >> d;
query[i] = {c, {a, d}};
}
if(c == 'C'){
int a; cin >> a;
query[i] = {c, {a, a}};
}
}
decompose(1);
for(int i = 1; i <= m; i++){
if(query[i].f == 'S'){
union_sets(query[i].s.f, query[i].s.s);
continue;
}
if(query[i].f == 'Q'){
int a = query[i].s.f, d = query[i].s.s;
if(Query(a, d) && find_set(a) == find_set(d)) cout << "yes\n";
else cout << "no\n";
}
if(query[i].f == 'C'){
int a = query[i].s.f;
cout << Count(a, i) << '\n';
}
}
return 0;
}
Compilation message
servers.cpp:24: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
24 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
194 ms |
316220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
194 ms |
316220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
316336 KB |
Output is correct |
| 2 |
Correct |
487 ms |
353528 KB |
Output is correct |
| 3 |
Correct |
516 ms |
353560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
316336 KB |
Output is correct |
| 2 |
Correct |
487 ms |
353528 KB |
Output is correct |
| 3 |
Correct |
516 ms |
353560 KB |
Output is correct |
| 4 |
Correct |
172 ms |
316264 KB |
Output is correct |
| 5 |
Correct |
512 ms |
353368 KB |
Output is correct |
| 6 |
Correct |
424 ms |
352628 KB |
Output is correct |
| 7 |
Correct |
423 ms |
352860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
316220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
316220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
191 ms |
316308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
191 ms |
316308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
316344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
316344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
316232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
316232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
