Submission #854888

#	Time	Username	Problem	Language	Result	Execution time	Memory
854888		khanhtai	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	5448 ms	692280 KiB

wild_boar

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "wildboar"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef pair<ii,ii> iv;
const int MAXN = 2103;
int plan[100005];
int n,m,q,l,u,v;
struct path{
    int s,e,w;
    path(int _s,int _e,int _w){
        s = _s;
        e = _e;
        w = _w;
    }
    path(){
        s = e = w = 0;
    }
};
int f(int x){return (((x-1)^1)+1);}

vector<int> g[MAXN];
vector<path> option[MAXN][MAXN];
vector<path> tmp,res;
int from[2*MAXN],to[2*MAXN],w[2*MAXN],dist[2*MAXN],cnt[2*MAXN];
bool visited[MAXN*2];
void eliminate(vector<path>&e){
    res.clear();
    res.shrink_to_fit();
    for(int times=1;times<=5;times++){
        path t = path(0,0,INF);
        for(auto p: e){
            int samestart=0,sameend=0,sameboth=0;
            for(auto cur: res){
                if (p.s == cur.s) samestart++;
                if (p.e == cur.e) sameend++;
                if (p.e == cur.e and p.s == cur.s) sameboth++;
            }
            if (samestart >= 2 or sameend >= 2 or sameboth>=1) continue;
            if (p.w < t.w) t=p;
        }
        res.pb(t);
    }
    e = res;
    e.shrink_to_fit();
}
vector<path> st[400005];
void unite(int node){
    st[node].clear();
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if (st[node<<1][i].e != st[node<<1|1][j].s){
                st[node].pb(path(st[node<<1][i].s,st[node<<1|1][j].e, st[node<<1][i].w + st[node<<1|1][j].w));
            }
        }
    }
    eliminate(st[node]);
}
void build(int node,int l,int r){
    if (l+1==r){
       st[node] = option[plan[l]][plan[r]];
       return;
    }
    int mid = (l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid,r);
    unite(node);
}
void update(int node,int l,int r,int pos,int val){
    if (l+1==r and l==pos){
        plan[pos] = val;
        st[node] = option[plan[l]][plan[r]];
        return;
    }
    if (l+1==r and r==pos){
        plan[pos] = val;
        st[node] = option[plan[l]][plan[r]];
        return;
    }
    int mid = (l+r)>>1;
    if (pos <= mid) update(node<<1,l,mid,pos,val);
    if (pos >= mid) update(node<<1|1,mid,r,pos,val);
    unite(node);
}
main()
{
    fast;
   // freopen(TASKNAME".inp","r",stdin);
   // freopen(TASKNAME".out","w",stdout);
    cin>>n>>m>>q>>l;
    for(int i=1;i<=m;i++){
        cin>>from[i*2]>>to[i*2]>>w[2*i];
        from[i*2-1] = to[i*2];
        to[i*2-1] = from[i*2];
        w[2*i-1] = w[i*2];
        g[from[i*2]].pb(2*i);
        g[to[i*2]].pb(2*i-1);
    }
    for(int i=1;i<=n;i++ ){
        for(auto edgeid: g[i]){
            for(int j=1;j<=2*m;j++){
                dist[j] = INF;
                cnt[j]=0;
                visited[j]=false;
            }
            priority_queue<ii,vector<ii>,greater<ii>> pq;

            dist[edgeid] = w[edgeid];

            pq.push({dist[edgeid],edgeid});
            while(!pq.empty()){
                int curedge = pq.top().se;
                int du = pq.top().fi;
                int node = to[curedge];
//                cerr<<i<<' '<<du<<' '<<node<<' '<<curedge<<endl;

                pq.pop();

                if (visited[curedge] or cnt[node] >= 2) continue;
                visited[curedge] = true;
                cnt[node]++;

                for(auto nxtedge: g[node]){
                    if (nxtedge == f(curedge)) continue;
                    if (dist[nxtedge] > dist[curedge] + w[nxtedge]){
                        dist[nxtedge] = dist[curedge] + w[nxtedge];
                        pq.push({dist[nxtedge],nxtedge});
                    }
                }
            }
            for(int j=1;j<=2*m;j++){
                option[from[edgeid]][to[j]].pb(path(edgeid,f(j),dist[j]));
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            eliminate(option[i][j]);
//            for(auto x: option[i][j]){
////                cout<<x.s<<' '<<x.e<<' '<<x.w<<endl;
//            }
//            cout<<endl;
        }
    }
    for(int i=1;i<=l;i++){
        cin>>plan[i];
    }
    build(1,1,l);
    for(int i=1;i<=q;i++){
        int p,k;
        cin>>p>>k;
        update(1,1,l,p,k);
        int ans = INF;
        for(auto x: st[1]){
            ans = min(ans,x.w);
        }
        if (ans == INF) cout<<-1<<endl;
        else cout<<ans<<endl;
    }


}

Compilation message (stderr)

wild_boar.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main()
      | ^~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:129:21: warning: unused variable 'du' [-Wunused-variable]
  129 |                 int du = pq.top().fi;
      |                     ^~

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38