답안 #60950 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60950	2018-07-25T04:09:56 Z	Benq	Wild Boar (JOI18_wild_boar)	C++11	12 / 100	317 ms	130056 KB

wild_boar

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 2001;

typedef array<ll,3> T; // distance, begin, end
T ori = {INF,INF,INF};
template<class T> void MN (T& a, T b) { a = min(a,b); }

struct dat {
    pi path;
    vector<T> besPath;
    dat() {}
    dat(pi _path, vector<T> _besPath) {
        path = _path;
        T mn = ori; for (auto a: _besPath) MN(mn,a);
        T bes[2][2]; F0R(i,2) F0R(j,2) bes[i][j] = ori;
        bes[0][0] = mn;
        for (auto a: _besPath) {
            if (a[1] == mn[1]) {
                if (a[2] != mn[2]) MN(bes[0][1],a);
            } else {
                MN(bes[1][0],a);
            }
        }
        for (auto a: _besPath) if (a[1] != mn[1] && a[2] != bes[1][0][2]) MN(bes[1][1],a);
        F0R(i,2) F0R(j,2) if (bes[i][j] != ori) besPath.pb(bes[i][j]);
    }
};

dat comb(const dat& l, const dat& r) {
    assert(l.path.s == r.path.f);
    
    vector<T> cand;
    for (auto a: l.besPath) for (auto b: r.besPath) if (a[2] != b[1]) 
        cand.pb({a[0]+b[0],a[1],b[2]});
        
    return dat({l.path.f,r.path.s},cand);
}

template<int SZ> struct Dijkstra {
    pl dist[SZ][2];
    vpi adj[SZ];
    
    void addEdge(int A, int B, int C) {
        adj[A].pb({B,C}), adj[B].pb({A,C});
    }
    
    void gen(T tmp) {
        F0R(i,SZ) F0R(j,2) dist[i][j] = {INF,INF};
        priority_queue<T,vector<T>,greater<T>> q;
        
        dist[tmp[2]][0] = {tmp[0],tmp[1]};
        q.push(tmp);
        
    	while (sz(q)) {
    		auto x = q.top(); q.pop();
    		
    		bool ok = 0;
    		F0R(j,2) if (dist[x[2]][j] == mp(x[0],x[1])) ok = 1;
    		if (!ok) continue;
    		
    		for (pi y: adj[x[2]]) {
    		    if (y.f == x[1]) continue;
    		    if (x[0]+y.s < dist[y.f][0].f) {
    		        if (dist[y.f][0].s != x[2]) dist[y.f][1] = dist[y.f][0];
        			dist[y.f][0] = {x[0]+y.s,x[2]};
        			q.push({x[0]+y.s,x[2],y.f});
    		    } else {
    		        if (x[2] == dist[y.f][0].s) continue;
    		        if (x[0]+y.s < dist[y.f][1].f) {
            			dist[y.f][1] = {x[0]+y.s,x[2]};
        			    q.push({x[0]+y.s,x[2],y.f});
    		        }
    		    }
    		}
    	}
    }
};

Dijkstra<MX> D;

int N,M,t,L;
dat d[MX][MX];

void init() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> t >> L;
    F0R(i,M) {
        int A,B,C; cin >> A >> B >> C; 
        D.addEdge(A,B,C);
    }
}

ll get(vl X) {
    dat z = d[X[0]][X[1]];
    FOR(i,2,sz(X)) z = comb(z,d[X[i-1]][X[i]]);
    /*if (sz(X) == 3) {
        for (auto a: d[2][1].besPath) {
            cout << a[0] << " " << a[1] << " " << a[2] << "\n";
        }
        cout << "HI " << z.path.f << " " << z.path.s << "\n";
        for (auto a: z.besPath) cout << a[0] << " " << a[1] << " " << a[2] << "\n";
        exit(0);
    }*/
    ll ans = INF;
    for (auto a: z.besPath) ans = min(ans,a[0]);
    if (ans == INF) ans = -1;
    return ans;
}

int main() {
    init();
    vector<T> path[MX];
    FOR(i,1,N+1) {
        for (pi j: D.adj[i]) {
            D.gen({j.s,i,j.f});
            FOR(k,1,N+1) if (k != i)
                F0R(z,2) if (D.dist[k][z].f != INF) 
                    path[k].pb({D.dist[k][z].f,j.f,D.dist[k][z].s});
        }
        
        FOR(k,1,N+1) if (k != i) {
            /*if (k == 1) {
                for (auto a: path[k]) cout << "HI " << a[0] << " " << a[1] << " " << a[2] << "\n";
            }*/
            d[i][k] = dat({i,k},path[k]);
            /*if (k == 1) {
                for (auto a: d[i][k].besPath) cout << "hi " << a[0] << " " << a[1] << " " << a[2] << "\n";
                exit(0);
            }*/
            path[k].clear();
        }
    }
    
    vl X(L); F0R(i,L) cin >> X[i];
    F0R(i,t) {
        int p,q; cin >> p >> q;
        X[p-1] = q;
        /*FOR(j,2,sz(X)+1) {
            vl XX = vl(X.begin(),X.begin()+j);
            cout << get(XX) << "\n";
        }*/
        cout << get(X) << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	122 ms	125816 KB	Output is correct
2	Correct	120 ms	125948 KB	Output is correct
3	Correct	128 ms	125992 KB	Output is correct
4	Correct	135 ms	125992 KB	Output is correct
5	Correct	143 ms	126048 KB	Output is correct
6	Correct	146 ms	126048 KB	Output is correct
7	Correct	154 ms	126048 KB	Output is correct
8	Correct	141 ms	126048 KB	Output is correct
9	Correct	149 ms	126048 KB	Output is correct
10	Correct	143 ms	126116 KB	Output is correct
11	Correct	151 ms	126192 KB	Output is correct
12	Correct	137 ms	126192 KB	Output is correct
13	Correct	139 ms	126192 KB	Output is correct
14	Correct	141 ms	126192 KB	Output is correct
15	Correct	132 ms	126196 KB	Output is correct
16	Correct	136 ms	126220 KB	Output is correct
17	Correct	123 ms	126220 KB	Output is correct
18	Correct	132 ms	126268 KB	Output is correct
19	Correct	134 ms	126268 KB	Output is correct
20	Correct	130 ms	126268 KB	Output is correct
21	Correct	118 ms	126268 KB	Output is correct
22	Correct	134 ms	126484 KB	Output is correct
23	Correct	130 ms	126484 KB	Output is correct
24	Correct	140 ms	126484 KB	Output is correct
25	Correct	146 ms	126484 KB	Output is correct

Subtask #2
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	122 ms	125816 KB	Output is correct
2	Correct	120 ms	125948 KB	Output is correct
3	Correct	128 ms	125992 KB	Output is correct
4	Correct	135 ms	125992 KB	Output is correct
5	Correct	143 ms	126048 KB	Output is correct
6	Correct	146 ms	126048 KB	Output is correct
7	Correct	154 ms	126048 KB	Output is correct
8	Correct	141 ms	126048 KB	Output is correct
9	Correct	149 ms	126048 KB	Output is correct
10	Correct	143 ms	126116 KB	Output is correct
11	Correct	151 ms	126192 KB	Output is correct
12	Correct	137 ms	126192 KB	Output is correct
13	Correct	139 ms	126192 KB	Output is correct
14	Correct	141 ms	126192 KB	Output is correct
15	Correct	132 ms	126196 KB	Output is correct
16	Correct	136 ms	126220 KB	Output is correct
17	Correct	123 ms	126220 KB	Output is correct
18	Correct	132 ms	126268 KB	Output is correct
19	Correct	134 ms	126268 KB	Output is correct
20	Correct	130 ms	126268 KB	Output is correct
21	Correct	118 ms	126268 KB	Output is correct
22	Correct	134 ms	126484 KB	Output is correct
23	Correct	130 ms	126484 KB	Output is correct
24	Correct	140 ms	126484 KB	Output is correct
25	Correct	146 ms	126484 KB	Output is correct
26	Correct	136 ms	126484 KB	Output is correct
27	Correct	161 ms	128584 KB	Output is correct
28	Correct	143 ms	128856 KB	Output is correct
29	Incorrect	317 ms	130056 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	122 ms	125816 KB	Output is correct
2	Correct	120 ms	125948 KB	Output is correct
3	Correct	128 ms	125992 KB	Output is correct
4	Correct	135 ms	125992 KB	Output is correct
5	Correct	143 ms	126048 KB	Output is correct
6	Correct	146 ms	126048 KB	Output is correct
7	Correct	154 ms	126048 KB	Output is correct
8	Correct	141 ms	126048 KB	Output is correct
9	Correct	149 ms	126048 KB	Output is correct
10	Correct	143 ms	126116 KB	Output is correct
11	Correct	151 ms	126192 KB	Output is correct
12	Correct	137 ms	126192 KB	Output is correct
13	Correct	139 ms	126192 KB	Output is correct
14	Correct	141 ms	126192 KB	Output is correct
15	Correct	132 ms	126196 KB	Output is correct
16	Correct	136 ms	126220 KB	Output is correct
17	Correct	123 ms	126220 KB	Output is correct
18	Correct	132 ms	126268 KB	Output is correct
19	Correct	134 ms	126268 KB	Output is correct
20	Correct	130 ms	126268 KB	Output is correct
21	Correct	118 ms	126268 KB	Output is correct
22	Correct	134 ms	126484 KB	Output is correct
23	Correct	130 ms	126484 KB	Output is correct
24	Correct	140 ms	126484 KB	Output is correct
25	Correct	146 ms	126484 KB	Output is correct
26	Correct	136 ms	126484 KB	Output is correct
27	Correct	161 ms	128584 KB	Output is correct
28	Correct	143 ms	128856 KB	Output is correct
29	Incorrect	317 ms	130056 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	122 ms	125816 KB	Output is correct
2	Correct	120 ms	125948 KB	Output is correct
3	Correct	128 ms	125992 KB	Output is correct
4	Correct	135 ms	125992 KB	Output is correct
5	Correct	143 ms	126048 KB	Output is correct
6	Correct	146 ms	126048 KB	Output is correct
7	Correct	154 ms	126048 KB	Output is correct
8	Correct	141 ms	126048 KB	Output is correct
9	Correct	149 ms	126048 KB	Output is correct
10	Correct	143 ms	126116 KB	Output is correct
11	Correct	151 ms	126192 KB	Output is correct
12	Correct	137 ms	126192 KB	Output is correct
13	Correct	139 ms	126192 KB	Output is correct
14	Correct	141 ms	126192 KB	Output is correct
15	Correct	132 ms	126196 KB	Output is correct
16	Correct	136 ms	126220 KB	Output is correct
17	Correct	123 ms	126220 KB	Output is correct
18	Correct	132 ms	126268 KB	Output is correct
19	Correct	134 ms	126268 KB	Output is correct
20	Correct	130 ms	126268 KB	Output is correct
21	Correct	118 ms	126268 KB	Output is correct
22	Correct	134 ms	126484 KB	Output is correct
23	Correct	130 ms	126484 KB	Output is correct
24	Correct	140 ms	126484 KB	Output is correct
25	Correct	146 ms	126484 KB	Output is correct
26	Correct	136 ms	126484 KB	Output is correct
27	Correct	161 ms	128584 KB	Output is correct
28	Correct	143 ms	128856 KB	Output is correct
29	Incorrect	317 ms	130056 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #60950

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 35.0

Subtask #3 0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 35.0

Subtask #3
0 / 15.0

Subtask #4
0 / 38.0