Submission #901534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
901534	2024-01-09T14:13:16 Z	pcc	Rigged Roads (NOI19_riggedroads)	C++14	Compilation error	0 ms	0 KB

riggedroads

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 3e5+10;
pii edges[mxn];
int N,M;
vector<int> paths[mxn*30];
int ppp;
bitset<mxn> need;

int newnode(){
	return ++ppp;
}


namespace TREE{

vector<pii> tree[mxn];
int par[mxn][20],vid[mxn][20],dep[mxn];

void dfs(int now){
	for(int i = 1;i<20;i++){
		par[now][i] = par[par[now][i-1]][i-1];
		vid[now][i] = newnode();
		paths[vid[now][i]].push_back(vid[now][i-1]);
		paths[vid[now][i]].push_back(vid[par[now][i-1]][i-1]);
	}
	for(auto nxt:tree[now]){
		if(nxt.fs == par[now][0])continue;
		par[nxt.fs][0] = now;
		vid[nxt.fs][0] = nxt.sc;
		dep[nxt.fs] = dep[now]+1;
		dfs(nxt.fs);
	}
	return;
}

void GO(){
	par[1][0] = 1;
	dfs(1);
}

void add_edge(int a,int b,int from){
	if(dep[a]<dep[b])swap(a,b);
	int d = dep[a]-dep[b];
	for(int i = 19;i>=0;i--){
		if(d&(1<<i)){
			paths[from].push_back(vid[a][i]);
			a = par[a][i];
		}
	}
	for(int i = 19;i>=0;i--){
		if(par[a][i] != par[b][i]){
			paths[from].push_back(vid[a][i]);
			paths[from].push_back(vid[b][i]);
			a = par[a][i];
			b = par[b][i];
		}
	}
	if(a != b){
		paths[from].push_back(vid[a][0]);
		paths[from].push_back(vid[b][0]);
	}
	return;
}

}

namespace DAG{

int deg[mxn*30];
int ans[mxn];

void TOPO(){
	priority_queue<pii,vector<pii>,less<pii>> pq;
	int C = M;
	for(int i = 0;i<=ppp;i++){
		for(auto nxt:paths[i]){
			//cout<<i<<','<<nxt<<endl;
			deg[nxt]++;
		}
	}
	for(int i = 0;i<=ppp;i++){
		if(!deg[i]){
			if(i>=1&&i<=M)pq.push(make_pair(i,i));
			else pq.push(make_pair(mxn,i));
		}
	}
	while(!pq.empty()){
		auto now = pq.top().sc;
		pq.pop();
		if(now>=1&&now<=M){
			ans[now] = C--;
		}
		for(auto nxt:paths[now]){
			deg[nxt]--;
			if(!deg[nxt]){
				if(nxt>=1&&nxt<=M)pq.push({nxt,nxt});
				else pq.push({mxn,nxt});
			}
		}
	}
	return;
}

void GET(){
	for(int i = 1;i<=M;i++)assert(ans[i]);
	for(int i = 1;i<=M;i++)cout<<ans[i]<<' ';cout<<'\n';
	return;
}

}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	ppp = M+1;
	for(auto &i:paths)i.push_back({1,1});
	return 0;
	for(int i = 1;i<=M;i++){
		cin>>edges[i].fs>>edges[i].sc;
	}
	for(int i = 1;i<N;i++){
		int id;
		cin>>id;
		need[id] = true;
		TREE::tree[edges[id].fs].push_back({edges[id].sc,id});
		TREE::tree[edges[id].sc].push_back({edges[id].fs,id});
	}
	TREE::GO();
	for(int i = 1;i<=M;i++){
		if(!need[i])TREE::add_edge(edges[i].fs,edges[i].sc,i);
	}
	DAG::TOPO();
	DAG::GET();
}

Compilation message

riggedroads.cpp: In function 'void DAG::GET()':
riggedroads.cpp:115:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  115 |  for(int i = 1;i<=M;i++)cout<<ans[i]<<' ';cout<<'\n';
      |  ^~~
riggedroads.cpp:115:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  115 |  for(int i = 1;i<=M;i++)cout<<ans[i]<<' ';cout<<'\n';
      |                                           ^~~~
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:125:37: error: no matching function for call to 'std::vector<int>::push_back(<brace-enclosed initializer list>)'
  125 |  for(auto &i:paths)i.push_back({1,1});
      |                                     ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from riggedroads.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const int&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<int>::value_type&&' {aka 'int&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~