답안 #60968 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60968	2018-07-25T04:39:19 Z	Benq	Wild Boar (JOI18_wild_boar)	C++11	62 / 100	18000 ms	494612 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 bes[4]; F0R(i,4) bes[i] = ori;
        for (auto a: _besPath) MN(bes[0],a);
        for (auto a: _besPath) if (a[1] != bes[0][1] || a[2] != bes[0][2]) MN(bes[1],a);
        
        /*if (bes[0][1] == bes[1][1] && bes[0][2] == bes[1][2]) {
           cout << "AH " << path.f << " " << path.s << " " << bes[0][1] << " " << bes[0][2];
           exit(0);
        }*/
       
        if (bes[0][1] == bes[1][1]) { // same x 
            for (auto a: _besPath) if (a[1] != bes[0][1]) MN(bes[2],a);
            for (auto a: _besPath) if (a[1] != bes[0][1] && a[2] != bes[2][2]) MN(bes[3],a);
        } else if (bes[0][2] == bes[1][2]) { // same y 
            for (auto a: _besPath) if (a[2] != bes[0][2]) MN(bes[2],a);
            for (auto a: _besPath) if (a[1] != bes[2][1] && a[2] != bes[0][2]) MN(bes[3],a);
        } else {
            for (auto a: _besPath) if (a[1] != bes[0][1] && a[2] != bes[1][2]) MN(bes[2],a);
            for (auto a: _besPath) if (a[1] != bes[1][1] && a[2] != bes[0][2]) MN(bes[3],a);
        }
        F0R(i,4) if (bes[i][0] != INF) besPath.pb(bes[i]);
    }
};

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]]);
    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	146 ms	125816 KB	Output is correct
2	Correct	135 ms	125956 KB	Output is correct
3	Correct	131 ms	126128 KB	Output is correct
4	Correct	141 ms	126128 KB	Output is correct
5	Correct	148 ms	126128 KB	Output is correct
6	Correct	142 ms	126128 KB	Output is correct
7	Correct	146 ms	126128 KB	Output is correct
8	Correct	138 ms	126128 KB	Output is correct
9	Correct	133 ms	126128 KB	Output is correct
10	Correct	137 ms	126128 KB	Output is correct
11	Correct	142 ms	126164 KB	Output is correct
12	Correct	147 ms	126164 KB	Output is correct
13	Correct	145 ms	126176 KB	Output is correct
14	Correct	135 ms	126176 KB	Output is correct
15	Correct	141 ms	126176 KB	Output is correct
16	Correct	143 ms	126176 KB	Output is correct
17	Correct	144 ms	126176 KB	Output is correct
18	Correct	138 ms	126176 KB	Output is correct
19	Correct	127 ms	126176 KB	Output is correct
20	Correct	153 ms	126176 KB	Output is correct
21	Correct	148 ms	126188 KB	Output is correct
22	Correct	122 ms	126228 KB	Output is correct
23	Correct	142 ms	126228 KB	Output is correct
24	Correct	122 ms	126228 KB	Output is correct
25	Correct	149 ms	126228 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	146 ms	125816 KB	Output is correct
2	Correct	135 ms	125956 KB	Output is correct
3	Correct	131 ms	126128 KB	Output is correct
4	Correct	141 ms	126128 KB	Output is correct
5	Correct	148 ms	126128 KB	Output is correct
6	Correct	142 ms	126128 KB	Output is correct
7	Correct	146 ms	126128 KB	Output is correct
8	Correct	138 ms	126128 KB	Output is correct
9	Correct	133 ms	126128 KB	Output is correct
10	Correct	137 ms	126128 KB	Output is correct
11	Correct	142 ms	126164 KB	Output is correct
12	Correct	147 ms	126164 KB	Output is correct
13	Correct	145 ms	126176 KB	Output is correct
14	Correct	135 ms	126176 KB	Output is correct
15	Correct	141 ms	126176 KB	Output is correct
16	Correct	143 ms	126176 KB	Output is correct
17	Correct	144 ms	126176 KB	Output is correct
18	Correct	138 ms	126176 KB	Output is correct
19	Correct	127 ms	126176 KB	Output is correct
20	Correct	153 ms	126176 KB	Output is correct
21	Correct	148 ms	126188 KB	Output is correct
22	Correct	122 ms	126228 KB	Output is correct
23	Correct	142 ms	126228 KB	Output is correct
24	Correct	122 ms	126228 KB	Output is correct
25	Correct	149 ms	126228 KB	Output is correct
26	Correct	144 ms	126228 KB	Output is correct
27	Correct	136 ms	128136 KB	Output is correct
28	Correct	135 ms	128136 KB	Output is correct
29	Correct	299 ms	128984 KB	Output is correct
30	Correct	290 ms	129152 KB	Output is correct
31	Correct	292 ms	130036 KB	Output is correct
32	Correct	244 ms	130156 KB	Output is correct
33	Correct	323 ms	131284 KB	Output is correct
34	Correct	322 ms	131628 KB	Output is correct
35	Correct	288 ms	132596 KB	Output is correct
36	Correct	284 ms	132668 KB	Output is correct
37	Correct	324 ms	132668 KB	Output is correct
38	Correct	316 ms	134620 KB	Output is correct
39	Correct	326 ms	135492 KB	Output is correct
40	Correct	395 ms	135492 KB	Output is correct
41	Correct	360 ms	135560 KB	Output is correct
42	Correct	335 ms	137792 KB	Output is correct
43	Correct	372 ms	138656 KB	Output is correct
44	Correct	371 ms	138864 KB	Output is correct
45	Correct	264 ms	138864 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	146 ms	125816 KB	Output is correct
2	Correct	135 ms	125956 KB	Output is correct
3	Correct	131 ms	126128 KB	Output is correct
4	Correct	141 ms	126128 KB	Output is correct
5	Correct	148 ms	126128 KB	Output is correct
6	Correct	142 ms	126128 KB	Output is correct
7	Correct	146 ms	126128 KB	Output is correct
8	Correct	138 ms	126128 KB	Output is correct
9	Correct	133 ms	126128 KB	Output is correct
10	Correct	137 ms	126128 KB	Output is correct
11	Correct	142 ms	126164 KB	Output is correct
12	Correct	147 ms	126164 KB	Output is correct
13	Correct	145 ms	126176 KB	Output is correct
14	Correct	135 ms	126176 KB	Output is correct
15	Correct	141 ms	126176 KB	Output is correct
16	Correct	143 ms	126176 KB	Output is correct
17	Correct	144 ms	126176 KB	Output is correct
18	Correct	138 ms	126176 KB	Output is correct
19	Correct	127 ms	126176 KB	Output is correct
20	Correct	153 ms	126176 KB	Output is correct
21	Correct	148 ms	126188 KB	Output is correct
22	Correct	122 ms	126228 KB	Output is correct
23	Correct	142 ms	126228 KB	Output is correct
24	Correct	122 ms	126228 KB	Output is correct
25	Correct	149 ms	126228 KB	Output is correct
26	Correct	144 ms	126228 KB	Output is correct
27	Correct	136 ms	128136 KB	Output is correct
28	Correct	135 ms	128136 KB	Output is correct
29	Correct	299 ms	128984 KB	Output is correct
30	Correct	290 ms	129152 KB	Output is correct
31	Correct	292 ms	130036 KB	Output is correct
32	Correct	244 ms	130156 KB	Output is correct
33	Correct	323 ms	131284 KB	Output is correct
34	Correct	322 ms	131628 KB	Output is correct
35	Correct	288 ms	132596 KB	Output is correct
36	Correct	284 ms	132668 KB	Output is correct
37	Correct	324 ms	132668 KB	Output is correct
38	Correct	316 ms	134620 KB	Output is correct
39	Correct	326 ms	135492 KB	Output is correct
40	Correct	395 ms	135492 KB	Output is correct
41	Correct	360 ms	135560 KB	Output is correct
42	Correct	335 ms	137792 KB	Output is correct
43	Correct	372 ms	138656 KB	Output is correct
44	Correct	371 ms	138864 KB	Output is correct
45	Correct	264 ms	138864 KB	Output is correct
46	Correct	300 ms	138864 KB	Output is correct
47	Correct	2212 ms	170820 KB	Output is correct
48	Correct	2420 ms	215772 KB	Output is correct
49	Correct	3178 ms	254740 KB	Output is correct
50	Correct	3338 ms	263184 KB	Output is correct
51	Correct	3223 ms	265264 KB	Output is correct
52	Correct	3376 ms	265264 KB	Output is correct
53	Correct	3148 ms	265264 KB	Output is correct
54	Correct	3660 ms	265264 KB	Output is correct
55	Correct	3484 ms	265264 KB	Output is correct
56	Correct	3499 ms	269148 KB	Output is correct
57	Correct	3691 ms	294436 KB	Output is correct
58	Correct	4332 ms	322280 KB	Output is correct
59	Correct	4403 ms	352224 KB	Output is correct
60	Correct	4302 ms	384516 KB	Output is correct
61	Correct	4668 ms	419036 KB	Output is correct
62	Correct	4615 ms	455644 KB	Output is correct
63	Correct	4474 ms	494612 KB	Output is correct
64	Correct	2348 ms	494612 KB	Output is correct
65	Correct	2077 ms	494612 KB	Output is correct

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	146 ms	125816 KB	Output is correct
2	Correct	135 ms	125956 KB	Output is correct
3	Correct	131 ms	126128 KB	Output is correct
4	Correct	141 ms	126128 KB	Output is correct
5	Correct	148 ms	126128 KB	Output is correct
6	Correct	142 ms	126128 KB	Output is correct
7	Correct	146 ms	126128 KB	Output is correct
8	Correct	138 ms	126128 KB	Output is correct
9	Correct	133 ms	126128 KB	Output is correct
10	Correct	137 ms	126128 KB	Output is correct
11	Correct	142 ms	126164 KB	Output is correct
12	Correct	147 ms	126164 KB	Output is correct
13	Correct	145 ms	126176 KB	Output is correct
14	Correct	135 ms	126176 KB	Output is correct
15	Correct	141 ms	126176 KB	Output is correct
16	Correct	143 ms	126176 KB	Output is correct
17	Correct	144 ms	126176 KB	Output is correct
18	Correct	138 ms	126176 KB	Output is correct
19	Correct	127 ms	126176 KB	Output is correct
20	Correct	153 ms	126176 KB	Output is correct
21	Correct	148 ms	126188 KB	Output is correct
22	Correct	122 ms	126228 KB	Output is correct
23	Correct	142 ms	126228 KB	Output is correct
24	Correct	122 ms	126228 KB	Output is correct
25	Correct	149 ms	126228 KB	Output is correct
26	Correct	144 ms	126228 KB	Output is correct
27	Correct	136 ms	128136 KB	Output is correct
28	Correct	135 ms	128136 KB	Output is correct
29	Correct	299 ms	128984 KB	Output is correct
30	Correct	290 ms	129152 KB	Output is correct
31	Correct	292 ms	130036 KB	Output is correct
32	Correct	244 ms	130156 KB	Output is correct
33	Correct	323 ms	131284 KB	Output is correct
34	Correct	322 ms	131628 KB	Output is correct
35	Correct	288 ms	132596 KB	Output is correct
36	Correct	284 ms	132668 KB	Output is correct
37	Correct	324 ms	132668 KB	Output is correct
38	Correct	316 ms	134620 KB	Output is correct
39	Correct	326 ms	135492 KB	Output is correct
40	Correct	395 ms	135492 KB	Output is correct
41	Correct	360 ms	135560 KB	Output is correct
42	Correct	335 ms	137792 KB	Output is correct
43	Correct	372 ms	138656 KB	Output is correct
44	Correct	371 ms	138864 KB	Output is correct
45	Correct	264 ms	138864 KB	Output is correct
46	Correct	300 ms	138864 KB	Output is correct
47	Correct	2212 ms	170820 KB	Output is correct
48	Correct	2420 ms	215772 KB	Output is correct
49	Correct	3178 ms	254740 KB	Output is correct
50	Correct	3338 ms	263184 KB	Output is correct
51	Correct	3223 ms	265264 KB	Output is correct
52	Correct	3376 ms	265264 KB	Output is correct
53	Correct	3148 ms	265264 KB	Output is correct
54	Correct	3660 ms	265264 KB	Output is correct
55	Correct	3484 ms	265264 KB	Output is correct
56	Correct	3499 ms	269148 KB	Output is correct
57	Correct	3691 ms	294436 KB	Output is correct
58	Correct	4332 ms	322280 KB	Output is correct
59	Correct	4403 ms	352224 KB	Output is correct
60	Correct	4302 ms	384516 KB	Output is correct
61	Correct	4668 ms	419036 KB	Output is correct
62	Correct	4615 ms	455644 KB	Output is correct
63	Correct	4474 ms	494612 KB	Output is correct
64	Correct	2348 ms	494612 KB	Output is correct
65	Correct	2077 ms	494612 KB	Output is correct
66	Correct	11022 ms	494612 KB	Output is correct
67	Correct	802 ms	494612 KB	Output is correct
68	Correct	1445 ms	494612 KB	Output is correct
69	Correct	2078 ms	494612 KB	Output is correct
70	Execution timed out	18077 ms	494612 KB	Time limit exceeded
71	Halted	0 ms	0 KB	-

답안 #60968

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 38.0