| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 676519 | vjudge1 | Worm Worries (BOI18_worm) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define f first
#define s second
#define pb push_back
#define endl '\n'
const ll maxn = 1e5+5;
const ll inf = (1ll<<60);
vector<int> graph(maxn);
vector<int> rgraph[maxn];
vector<bool> occ(maxn);
int dpt[maxn][2];
int dpc[maxn][3];
vector<bool> incyc(maxn);
vector<int> siz(maxn);
vector<int> cycs;
void dfs(int x){
if (incyc[graph[x]]) {
incyc[x]=1;
return;
}
if (occ[graph[x]]==0) {
occ[graph[x]]=1;
dfs(graph[x]);
incyc[x]=1;
}
else {
cycs.pb(x);
incyc[x]=1;
}
}
void dfs2(int x){
int mn=0;
REP(i, SZ(rgraph[x])){
if (incyc[rgraph[x][i]]) continue;
dfs2(rgraph[x][i]);
dpt[x][0]+=dpt[rgraph[x][i]][1];
dpt[x][1]+=dpt[rgraph[x][i]][1];
mn=min(mn, dpt[rgraph[x][i]][0]-dpt[rgraph[x][i]][1]);
}
dpt[x][1]+=mn+1;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin>>n;
vector<string> pos(n);
vector<pair<string, string> > Graph(n);
REP(i, n){
cin>>Graph[i].f>>Graph[i].s;
pos[i]=Graph[i].f;
}
sort(ALL(pos));
REP(i, n){
int a=upper_bound(ALL(pos), Graph[i].f)-pos.begin();
int b=upper_bound(ALL(pos), Graph[i].s)-pos.begin();
graph[a]=b;
rgraph[b].pb(a);
}
REP1(i, n){
if (!occ[i]){
occ[i]=1;
dfs(i);
}
}
int ans=0;
fill(ALL(incyc), false);
REP(i, SZ(cycs)){
int cur = cycs[i];
//cout<<cur<<endl;
vector<pii> tmp;
incyc[cur]=1;
cur=graph[cur];
while(cur!=cycs[i]){
incyc[cur]=1;
cur=graph[cur];
}
dfs2(cur);
tmp.pb({dpt[cur][0], dpt[cur][1]});
cur=graph[cur];
while(cur!=cycs[i]){
dfs2(cur);
tmp.pb({dpt[cur][0], dpt[cur][1]});
cur=graph[cur];
}
if (SZ(tmp)==1){
ans+=tmp[0].s;
}
else if (SZ(tmp)==2){
ans+=min(tmp[0].f+tmp[1].f, tmp[0].s+tmp[1].s);
}
else {
int cans = inf;
// first is 0
dpc[0][0]=tmp[0].f;
dpc[0][1]=dpc[0][2]=inf;
REP1(j, SZ(tmp)-1){
dpc[j][0]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].f);
dpc[j][1]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].s);
dpc[j][2]=min(inf, dpc[j-1][0]+tmp[j].f+1);
}
cans=min({cans, dpc[SZ(tmp)-1][1], dpc[SZ(tmp)-1][2]});
// second is 1
dpc[0][1]=tmp[0].s;
dpc[0][0]=dpc[0][2]=inf;
REP1(j, SZ(tmp)-1){
dpc[j][0]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].f);
dpc[j][1]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].s);
dpc[j][2]=min(inf, dpc[j-1][0]+tmp[j].f+1);
}
cans=min({cans, dpc[SZ(tmp)-1][1], dpc[SZ(tmp)-1][2]});
// third is 2
dpc[0][2]=tmp[0].f+1;
dpc[0][0]=dpc[0][1]=inf;
REP1(j, SZ(tmp)-1){
dpc[j][0]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].f);
dpc[j][1]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].s);
dpc[j][2]=min(inf, dpc[j-1][0]+tmp[j].f+1);
}
cans=min(cans, dpc[SZ(tmp)-1][0]);
ans+=cans;
}
}
if (n1) ans=-1;
cout<<ans<<endl;
}