QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #278236 | #6872. Magma Cave | anhduc2701 | TL | 0ms | 0kb | C++20 | 3.9kb | 2023-12-07 14:00:41 | 2023-12-07 14:00:41 |
answer
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int blk=500;
const i64 oo = 1e18;
int n,q;
struct edge{
int u,v,w;
edge(){}
edge(int _u,int _v,int _w){
u=_u, v=_v, w=_w;
}
}canh[maxn];
vector<int>Ga[maxn];
vector<int>Gb[maxn];
int pa[maxn];
int sz[maxn];
struct dsu{
int u,v;
dsu(){}
dsu(int _u,int _v){
u=_u;
v=_v;
}
};
int fin(int u){
if(pa[u]==u)return u;
return fin(pa[u]);
}
stack<dsu>s;
void rollback(){
dsu p=s.top();
s.pop();
sz[p.u]-=sz[p.v];
pa[p.v]=p.v;
}
bool join(int u,int v){
int x=fin(u);
int y=fin(v);
if(x==y)return false;
if(sz[x]<sz[y]){
swap(x,y);
}
sz[x]+=sz[y];
pa[y]=x;
s.push(dsu(x,y));
return true;
}
int mi[maxn];
int ma[maxn];
void solve() {
cin >> n >> q;
int last=0;
for(int i=1;i<=n;i++){
pa[i]=i;
sz[i]=1;
}
vector<int>idx;
for(int i=1;i<=q;i++){
int type,u,v,w;
cin >> type;
if (type == 1){
cin >> u >> v >> w;
idx.pb(i);
canh[i]=edge(u,v,w);
}
else{
int k;
cin >> k >> w;
canh[i]=edge(k,0,w);
}
if(idx.size()==blk || i==q){
vector<int>poi;
for(int j=1;j<=i;j++){
if(j<last && canh[j].v!=0){
poi.pb(canh[j].w);
}
else if(j>=last){
poi.pb(canh[j].w);
}
}
sort(poi.begin(),poi.end());
poi.resize(unique(poi.begin(),poi.end())-poi.begin());
for(int j=1;j<=i;j++){
int x=lower_bound(poi.begin(), poi.end(), canh[j].w)-poi.begin();
if(j<last && canh[j].v!=0){
Ga[x].pb(j);
}
else if(j>=last ){
if(canh[j].v==0)Gb[x].pb(j);
}
}
for(int j=0;j<(int)poi.size();j++){
for(auto v:Ga[j]){
join(canh[v].u,canh[v].v);
}
for(auto v:Gb[j]){
int cnt=0;
for(auto j:idx){
if(j>v)break;
if(canh[j].w<=canh[v].w){
cnt+=join(canh[j].u,canh[j].v);
}
}
ma[v]=s.size();
for(int j=1;j<=cnt;j++){
rollback();
}
}
}
while(s.size()){
rollback();
}
for(int j=poi.size()-1;j>=0;j--){
for(auto v:Ga[j]){
int cnt=0;
for(auto j:idx){
if(j>v)break;
if(canh[j].w>canh[v].w){
cnt+=join(canh[j].u,canh[j].v);
}
}
mi[v]=n-1-s.size();
for(int j=1;j<=cnt;j++){
rollback();
}
}
for(auto v:Gb[j]){
if(v<=last && canh[v].v!=0){
join(canh[v].u,canh[v].v);
}
}
Ga[j].clear();
Gb[j].clear();
}
while(s.size()){
rollback();
}
last=i;
idx.clear();
}
}
int cnt=n-1;
map<int,bool>xh;
for(int i=1;i<=q;i++){
if(canh[i].v!=0){
xh[canh[i].w]=1;
if(cnt!=0)cnt-=join(canh[i].u,canh[i].v);
}
else{
if(cnt==0 && mi[i]<=canh[i].u && canh[i].u<=ma[i] && xh.find(canh[i].w)!=xh.end()){
cout << "YES" << "\n";
}
else{
cout << "NO" << "\n";
}
}
}
}
signed main() {
#ifndef CDuongg
if(fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; cin >> t;
while(t--) {
solve();
}
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
100 500 1999 1 112 419 318 1 419 208 1700 1 208 255 603 1 255 202 306 1 202 54 326 1 54 468 1506 1 468 23 856 1 23 90 758 1 90 271 1104 1 271 442 1900 1 442 441 19 1 441 378 1227 1 378 466 24 1 466 186 228 1 186 399 1387 1 399 288 297 1 288 144 1763 1 144 418 1896 1 418 217 673 1 217 281 1259 1 281 ...
output:
NO NO YES NO NO NO NO YES YES NO YES YES NO NO YES NO NO YES NO YES YES YES YES NO YES YES NO YES NO YES YES YES YES NO YES YES NO NO NO NO NO YES YES YES NO NO NO YES NO NO YES NO NO NO NO YES NO YES NO NO YES NO NO NO YES NO YES NO YES NO YES YES NO YES NO NO YES YES YES YES NO NO NO YES YES NO NO...