이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
using namespace std;
///~~~~~~~~~~~~~~~~~~~~~~~~~~
template <typename H, typename T>
ostream& operator<<(ostream& os, pair<H, T> m){
return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H>
ostream& operator<<(ostream& os, vector<H> V){
os<<"{";
for(int i=0; i<V.size(); i++){
if(i)os<<" ";
os<<V[i];
}
os<<"}";
return os;
}
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#ifdef LOCAL
#define deb(x...) cerr<<#x<<" = ";debug(x);
#else
#define deb(...)
#endif
///~~~~~~~~~~~~~~~~~~~~~~~~~
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=2e5+5, INF=1e9+5, mod=1e9+7;
int typ[N], zera[N], bliska[N], dist2[N];
int licz[N];
ll tab[N], pref[N], pref2[N], dist[N];
vi E[N], co[N];
void solve(int n, int s, ll cost, bool b){
//cost--;
dist[s]=0;
licz[s]=0;
priority_queue<pair<ll, int> > Q;
if(b==1)Q.push({0, s});
else{
for(int i=1; i<=n; i++)
dist[i]+=cost*licz[i], Q.push({-dist[i], i});
}
while(Q.size()){
int v=Q.top().nd;
ll d=-Q.top().st;
Q.pop();
if(d!=dist[v])continue;
for(int u:E[v]){
if(dist[u]>dist[v]+1+typ[u]*cost){
dist[u]=dist[v]+1+typ[u]*cost;
licz[u]=licz[v]+typ[u];
Q.push({-dist[u], u});
}
}
}
}
int main(){
BOOST;
int n, m, k;
cin>>n>>m>>k;
//assert(n<=3000);
for(int i=0; i<m; i++){
int u, v;cin>>u>>v;
E[u].pb(v);
E[v].pb(u);
}
string s;
cin>>s;
for(int i=0; i<n; i++)typ[i+1]=s[i]-'0';
for(int i=1; i<=n; i++){
zera[i]=1e9;
for(int u:E[i]){
if(typ[u] && typ[i])zera[i]=0;
}
}
vi V;
for(int i=1; i<=n; i++){
if(zera[i]==0)V.pb(i);
}
for(int i=0; i<V.size(); i++){
int v=V[i];
for(int u:E[v]){
if(zera[u]>zera[v]+1-typ[u]){
zera[u]=zera[v]+1-typ[u];
V.pb(u);
}
}
}
V.clear();
for(int i=1; i<=n; i++){
if(typ[i]==0)bliska[i]=1e9;
else V.pb(i);
}
for(int i=0; i<V.size(); i++){
int v=V[i];
for(int u:E[v]){
if(bliska[u]==1e9){
bliska[u]=bliska[v]+1;
V.pb(u);
}
}
}
for(int i=1; i<=n; i++){
deb(i, bliska[i], zera[i]);
}
vi X(k);
for(int &i:X)cin>>i;
deb(X);
for(int i=1; i<k; i++){
if(typ[X[i]]==1){
/*for(int j=1; j<n; j++){
tab[j]+=min(2*j, j+zera[X[i]]);
}*/
pref2[1]+=2;
if(zera[X[i]]!=1e9)pref2[zera[X[i]]+1]--;
}
else{
ll t=min(-1+bliska[X[i]], zera[X[i]]-1);
/*for(int j=1; j<n; j++){
//deb(j, 2*j-2+bliska[X[i]], j+zera[X[i]]);
tab[j]+=min(j-2+bliska[X[i]], zera[X[i]]-1)-t;
}*/
pref2[1]+=1;
pref[1]+=t;
if(zera[X[i]]-1 >t){
pref2[2]++;
if(zera[X[i]]!=1e9){
pref2[1+zera[X[i]]-t]--;
}
}
}
}
for(int i=0; i<n; i++){
pref2[i+1]+=pref2[i];
}
for(int i=0; i<n; i++){
pref[i+1]+=pref[i]+pref2[i+1];
}
for(int i=0; i<n; i++){
tab[i]+=pref[i];
}
vector<ll> ans(n+1, 1e18);
ans[X[0]]=0;
for(int i=1; i<=n; i++)dist[i]=1e9;
dist[X[0]]=0;
vector<int> changed={X[0]};
for(int ile=0; ile<2; ile++){//ile skokow
vi wazne;
for(int i:changed){
if(dist[i]!=1e9){
co[dist[i]].pb(i);
wazne.pb(dist[i]);
}
}
sort(all(wazne));
changed.clear();
vii todo;
for(int d:wazne){
while(co[d].size()){
for(int v:co[d]){
for(int u:E[v]){
if(typ[u]==0 && dist[u]>dist[v]+1){
changed.pb(u);
dist[u]=dist[v]+1;
co[dist[u]].pb(u);
}
if(typ[u]==1 && dist[v]<dist[u]){
todo.pb({dist[v], u});
//dist[u]=dist[v];
changed.pb(u);
}
}
}
co[d].clear();
d++;
}
}
sort(all(todo));
reverse(all(todo));
for(pii i:todo){
dist[i.nd]=i.st;
}
for(int i:changed){
if(dist[i]==1e9)continue;
if(i==1){
deb(ile, i, dist[i], tab[ile], typ[i],dist[i]+tab[ile]+typ[i]+ile);
}
if(ile<2)
ans[i]=min(ans[i], dist[i]+tab[ile]+typ[i]+ile);
}
}
for(int i=1; i<=n; i++){
dist[i]=1e9;
dist2[i]=1e9;
}
for(int i=1; i<=n; i++)dist[i]=1e18;
for(int i=1; i<n; i++){
deb(tab[i]);
if(i>1 && (i==2 || tab[i]-tab[i-1]!=tab[i-1]-tab[i-2])){
solve(n, X[0], tab[i]-tab[i-1], i==2);
ll cost=tab[i]-i*(tab[i]-tab[i-1]);
deb(i, dist[1], cost, tab[i]-tab[i-1]);
for(int j=1; j<=n; j++){
if(licz[j]-typ[j]>=i-1)
ans[j]=min(ans[j], dist[j]+cost-typ[j]*(tab[i]-tab[i-1]));
dist[j]-=licz[j]*(tab[i]-tab[i-1]);
}
}
}
ans[X[0]]=0;
for(int i=1; i<=n; i++){
cout<<ans[i]<<"\n";
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:114:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
Main.cpp:128:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |