Submission #1119630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119630		vjudge1	Senior Postmen (BOI14_postmen)	C++17	0 / 100	9 ms	12280 KiB

postmen

#include<bits/stdc++.h>

#define str string
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define em emplace
using namespace std;
const int N=5e5+5,lg=20,mod=1e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int n,m,st[N*4];
int sz[N];
vector<ii>a[N];
bool k[N];
vector<int>res;
void build(int id,int r,int l){
	if(r==l){
		st[id]=sz[r];
		return;
	}
	int mid=(r+l)>>1;
	build(id<<1,r,mid);
	build(id<<1|1,mid+1,l);
	st[id]=min(st[id<<1],st[id<<1|1]);
}
void update(int id,int r,int l,int i,int val){
	if(r==l){
		if(st[id]==1e9)return;
		st[id]+=val;
		if(st[id]==0)st[id]=1e9;
		return;
	}
	int mid=(r+l)>>1;
	if(mid>=i){
		update(id<<1,r,mid,i,val);
	}
	else update(id<<1|1,mid+1,l,i,val);
	st[id]=min(st[id<<1],st[id<<1|1]);
}
int get(int id,int r,int l,int i){
	if(r==l){
		return st[id];
	}
    int mid=(r+l)>>1;
    if(mid>=i)return get(id<<1,r,mid,i);
    else return get(id<<1|1,mid+1,l,i);
}
int getright(int id,int r,int l,int val){
	if(st[id]>val)return -1;
	if(r==l)return r;
	int mid=(r+l)>>1;
	int R=getright(id<<1,r,mid,val);
	if(R==-1)
		return getright(id<<1|1,mid+1,l,val);
	return R;
}
void bfs(int u){
   queue<int>p;
   p.push(u);
   // cout <<u;
   while(!p.empty()){
   	  u=p.front();
   	  res.emb(u);
   	  p.pop();
   	  // p.pop()
   	  int uv=0,j=0;
      for(ii v:a[u]){
      	if(k[v.se])continue;
      	if(j==0){
      		j=v.fi;uv=v.se;
      	}
      	if(get(1,1,n,j)>get(1,1,n,v.fi)){
      		j=v.fi;uv=v.se;
      	}
      }
      if(!j)continue;
      k[uv]=true;
      p.push(j);
      // cout <<u<<" "<<j<<'\n';
         	    update(1,1,n,u,-1);
         	    update(1,1,n,j,-1);
   }
 
}
void solve(){
    cin >> n >> m;
    sz[0]=1e9;
    for(int i=1;i<=m;++i){
    	int u,v;
    	cin >> u >> v;
    	a[u].emb(v,i);
    	a[v].emb(u,i);
    	sz[u]++;
    	sz[v]++;
    }
    for(int i=1;i<=n;++i){
    	if(sz[i]==0){
    		cout <<i<<'\n';
            sz[i]=1e9;
    	}
    }
    build(1,1,n);
    int f=5;
    while(f--&&st[1]<n){
    	int u=getright(1,1,n,st[1]);
    	bfs(u);
    	res.pop_back();
    	// for(int i=1;i<=n;++i)cout<<get(1,1,n,i)<<" ";
    		// cout<<'\n';
    	for(auto j:res){
    		cout <<j<<" ";
 
    	}
    	res.clear();
    	cout <<'\n';
    }
}
main()
{
	srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    int t=1;
 //   cin >> t;
while(t--){
    solve();
    // cout<<'\n';
}

}

Compilation message (stderr)

postmen.cpp:132:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  132 | main()
      | ^~~~
postmen.cpp: In function 'int main()':
postmen.cpp:139:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
postmen.cpp:140:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 38
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45