답안 #60973 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60973	2018-07-25T04:49:41 Z	Benq	Wild Boar (JOI18_wild_boar)	C++11	100 / 100	9782 ms	532032 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 = {-1,-1};
    vector<T> besPath;
    dat() {}
    ll get() {
        ll ans = INF;
        for (auto a: besPath) MN(ans,a[0]);
        if (ans == INF) return -1;
        return ans;
    }
    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;
vi X;
dat d[MX][MX], seg[1<<18];
 
dat COMB(const dat& l, const dat& r) {
    if (r.path.f == -1) return l;
    if (l.path.f == -1) return r;
    if (l.path.s != r.path.f) return comb(comb(l,d[l.path.s][r.path.f]),r);
    return comb(l,r);
}
 
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;
}

void upd(int x) {
    int ind = x^(1<<17);
    seg[ind] = d[X[x]][X[x+1]];
    for (ind /= 2; ind; ind /= 2) seg[ind] = COMB(seg[2*ind],seg[2*ind+1]);
}

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) {
            d[i][k] = dat({i,k},path[k]);
            path[k].clear();
        }
    }
    
    X.resize(L);
    F0R(i,L) cin >> X[i];
    F0R(i,sz(X)-1) seg[i^(1<<17)] = d[X[i]][X[i+1]];
    FORd(i,1,1<<17) seg[i] = COMB(seg[2*i],seg[2*i+1]);
    F0R(i,t) {
        int p,q; cin >> p >> q;
        X[p-1] = q;
        if (p > 1) upd(p-2);
        if (p < L) upd(p-1);
        cout << seg[1].get() << "\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	148 ms	134100 KB	Output is correct
2	Correct	143 ms	134100 KB	Output is correct
3	Correct	127 ms	134248 KB	Output is correct
4	Correct	154 ms	134272 KB	Output is correct
5	Correct	140 ms	134356 KB	Output is correct
6	Correct	148 ms	134356 KB	Output is correct
7	Correct	137 ms	134440 KB	Output is correct
8	Correct	155 ms	134440 KB	Output is correct
9	Correct	167 ms	134440 KB	Output is correct
10	Correct	165 ms	134440 KB	Output is correct
11	Correct	138 ms	134440 KB	Output is correct
12	Correct	132 ms	134440 KB	Output is correct
13	Correct	175 ms	134440 KB	Output is correct
14	Correct	131 ms	134440 KB	Output is correct
15	Correct	151 ms	134440 KB	Output is correct
16	Correct	147 ms	134440 KB	Output is correct
17	Correct	135 ms	134440 KB	Output is correct
18	Correct	151 ms	134440 KB	Output is correct
19	Correct	130 ms	134440 KB	Output is correct
20	Correct	166 ms	134440 KB	Output is correct
21	Correct	130 ms	134440 KB	Output is correct
22	Correct	143 ms	134440 KB	Output is correct
23	Correct	125 ms	134440 KB	Output is correct
24	Correct	125 ms	134440 KB	Output is correct
25	Correct	144 ms	134440 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	148 ms	134100 KB	Output is correct
2	Correct	143 ms	134100 KB	Output is correct
3	Correct	127 ms	134248 KB	Output is correct
4	Correct	154 ms	134272 KB	Output is correct
5	Correct	140 ms	134356 KB	Output is correct
6	Correct	148 ms	134356 KB	Output is correct
7	Correct	137 ms	134440 KB	Output is correct
8	Correct	155 ms	134440 KB	Output is correct
9	Correct	167 ms	134440 KB	Output is correct
10	Correct	165 ms	134440 KB	Output is correct
11	Correct	138 ms	134440 KB	Output is correct
12	Correct	132 ms	134440 KB	Output is correct
13	Correct	175 ms	134440 KB	Output is correct
14	Correct	131 ms	134440 KB	Output is correct
15	Correct	151 ms	134440 KB	Output is correct
16	Correct	147 ms	134440 KB	Output is correct
17	Correct	135 ms	134440 KB	Output is correct
18	Correct	151 ms	134440 KB	Output is correct
19	Correct	130 ms	134440 KB	Output is correct
20	Correct	166 ms	134440 KB	Output is correct
21	Correct	130 ms	134440 KB	Output is correct
22	Correct	143 ms	134440 KB	Output is correct
23	Correct	125 ms	134440 KB	Output is correct
24	Correct	125 ms	134440 KB	Output is correct
25	Correct	144 ms	134440 KB	Output is correct
26	Correct	148 ms	134440 KB	Output is correct
27	Correct	191 ms	139976 KB	Output is correct
28	Correct	185 ms	139976 KB	Output is correct
29	Correct	402 ms	157916 KB	Output is correct
30	Correct	298 ms	157948 KB	Output is correct
31	Correct	297 ms	158388 KB	Output is correct
32	Correct	391 ms	158388 KB	Output is correct
33	Correct	384 ms	159308 KB	Output is correct
34	Correct	330 ms	159552 KB	Output is correct
35	Correct	297 ms	160112 KB	Output is correct
36	Correct	362 ms	160112 KB	Output is correct
37	Correct	405 ms	160112 KB	Output is correct
38	Correct	338 ms	161184 KB	Output is correct
39	Correct	323 ms	161688 KB	Output is correct
40	Correct	322 ms	161688 KB	Output is correct
41	Correct	340 ms	161688 KB	Output is correct
42	Correct	331 ms	163112 KB	Output is correct
43	Correct	345 ms	163600 KB	Output is correct
44	Correct	369 ms	163752 KB	Output is correct
45	Correct	296 ms	163752 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	148 ms	134100 KB	Output is correct
2	Correct	143 ms	134100 KB	Output is correct
3	Correct	127 ms	134248 KB	Output is correct
4	Correct	154 ms	134272 KB	Output is correct
5	Correct	140 ms	134356 KB	Output is correct
6	Correct	148 ms	134356 KB	Output is correct
7	Correct	137 ms	134440 KB	Output is correct
8	Correct	155 ms	134440 KB	Output is correct
9	Correct	167 ms	134440 KB	Output is correct
10	Correct	165 ms	134440 KB	Output is correct
11	Correct	138 ms	134440 KB	Output is correct
12	Correct	132 ms	134440 KB	Output is correct
13	Correct	175 ms	134440 KB	Output is correct
14	Correct	131 ms	134440 KB	Output is correct
15	Correct	151 ms	134440 KB	Output is correct
16	Correct	147 ms	134440 KB	Output is correct
17	Correct	135 ms	134440 KB	Output is correct
18	Correct	151 ms	134440 KB	Output is correct
19	Correct	130 ms	134440 KB	Output is correct
20	Correct	166 ms	134440 KB	Output is correct
21	Correct	130 ms	134440 KB	Output is correct
22	Correct	143 ms	134440 KB	Output is correct
23	Correct	125 ms	134440 KB	Output is correct
24	Correct	125 ms	134440 KB	Output is correct
25	Correct	144 ms	134440 KB	Output is correct
26	Correct	148 ms	134440 KB	Output is correct
27	Correct	191 ms	139976 KB	Output is correct
28	Correct	185 ms	139976 KB	Output is correct
29	Correct	402 ms	157916 KB	Output is correct
30	Correct	298 ms	157948 KB	Output is correct
31	Correct	297 ms	158388 KB	Output is correct
32	Correct	391 ms	158388 KB	Output is correct
33	Correct	384 ms	159308 KB	Output is correct
34	Correct	330 ms	159552 KB	Output is correct
35	Correct	297 ms	160112 KB	Output is correct
36	Correct	362 ms	160112 KB	Output is correct
37	Correct	405 ms	160112 KB	Output is correct
38	Correct	338 ms	161184 KB	Output is correct
39	Correct	323 ms	161688 KB	Output is correct
40	Correct	322 ms	161688 KB	Output is correct
41	Correct	340 ms	161688 KB	Output is correct
42	Correct	331 ms	163112 KB	Output is correct
43	Correct	345 ms	163600 KB	Output is correct
44	Correct	369 ms	163752 KB	Output is correct
45	Correct	296 ms	163752 KB	Output is correct
46	Correct	297 ms	163752 KB	Output is correct
47	Correct	2171 ms	194636 KB	Output is correct
48	Correct	3037 ms	239568 KB	Output is correct
49	Correct	3199 ms	278312 KB	Output is correct
50	Correct	3517 ms	286528 KB	Output is correct
51	Correct	3327 ms	288236 KB	Output is correct
52	Correct	3610 ms	288236 KB	Output is correct
53	Correct	3144 ms	288236 KB	Output is correct
54	Correct	3352 ms	288236 KB	Output is correct
55	Correct	3357 ms	288236 KB	Output is correct
56	Correct	3742 ms	290312 KB	Output is correct
57	Correct	4040 ms	315204 KB	Output is correct
58	Correct	3949 ms	342528 KB	Output is correct
59	Correct	4173 ms	372220 KB	Output is correct
60	Correct	5167 ms	403812 KB	Output is correct
61	Correct	4612 ms	437896 KB	Output is correct
62	Correct	4599 ms	473980 KB	Output is correct
63	Correct	4891 ms	512588 KB	Output is correct
64	Correct	2130 ms	512588 KB	Output is correct
65	Correct	1937 ms	512588 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	148 ms	134100 KB	Output is correct
2	Correct	143 ms	134100 KB	Output is correct
3	Correct	127 ms	134248 KB	Output is correct
4	Correct	154 ms	134272 KB	Output is correct
5	Correct	140 ms	134356 KB	Output is correct
6	Correct	148 ms	134356 KB	Output is correct
7	Correct	137 ms	134440 KB	Output is correct
8	Correct	155 ms	134440 KB	Output is correct
9	Correct	167 ms	134440 KB	Output is correct
10	Correct	165 ms	134440 KB	Output is correct
11	Correct	138 ms	134440 KB	Output is correct
12	Correct	132 ms	134440 KB	Output is correct
13	Correct	175 ms	134440 KB	Output is correct
14	Correct	131 ms	134440 KB	Output is correct
15	Correct	151 ms	134440 KB	Output is correct
16	Correct	147 ms	134440 KB	Output is correct
17	Correct	135 ms	134440 KB	Output is correct
18	Correct	151 ms	134440 KB	Output is correct
19	Correct	130 ms	134440 KB	Output is correct
20	Correct	166 ms	134440 KB	Output is correct
21	Correct	130 ms	134440 KB	Output is correct
22	Correct	143 ms	134440 KB	Output is correct
23	Correct	125 ms	134440 KB	Output is correct
24	Correct	125 ms	134440 KB	Output is correct
25	Correct	144 ms	134440 KB	Output is correct
26	Correct	148 ms	134440 KB	Output is correct
27	Correct	191 ms	139976 KB	Output is correct
28	Correct	185 ms	139976 KB	Output is correct
29	Correct	402 ms	157916 KB	Output is correct
30	Correct	298 ms	157948 KB	Output is correct
31	Correct	297 ms	158388 KB	Output is correct
32	Correct	391 ms	158388 KB	Output is correct
33	Correct	384 ms	159308 KB	Output is correct
34	Correct	330 ms	159552 KB	Output is correct
35	Correct	297 ms	160112 KB	Output is correct
36	Correct	362 ms	160112 KB	Output is correct
37	Correct	405 ms	160112 KB	Output is correct
38	Correct	338 ms	161184 KB	Output is correct
39	Correct	323 ms	161688 KB	Output is correct
40	Correct	322 ms	161688 KB	Output is correct
41	Correct	340 ms	161688 KB	Output is correct
42	Correct	331 ms	163112 KB	Output is correct
43	Correct	345 ms	163600 KB	Output is correct
44	Correct	369 ms	163752 KB	Output is correct
45	Correct	296 ms	163752 KB	Output is correct
46	Correct	297 ms	163752 KB	Output is correct
47	Correct	2171 ms	194636 KB	Output is correct
48	Correct	3037 ms	239568 KB	Output is correct
49	Correct	3199 ms	278312 KB	Output is correct
50	Correct	3517 ms	286528 KB	Output is correct
51	Correct	3327 ms	288236 KB	Output is correct
52	Correct	3610 ms	288236 KB	Output is correct
53	Correct	3144 ms	288236 KB	Output is correct
54	Correct	3352 ms	288236 KB	Output is correct
55	Correct	3357 ms	288236 KB	Output is correct
56	Correct	3742 ms	290312 KB	Output is correct
57	Correct	4040 ms	315204 KB	Output is correct
58	Correct	3949 ms	342528 KB	Output is correct
59	Correct	4173 ms	372220 KB	Output is correct
60	Correct	5167 ms	403812 KB	Output is correct
61	Correct	4612 ms	437896 KB	Output is correct
62	Correct	4599 ms	473980 KB	Output is correct
63	Correct	4891 ms	512588 KB	Output is correct
64	Correct	2130 ms	512588 KB	Output is correct
65	Correct	1937 ms	512588 KB	Output is correct
66	Correct	307 ms	512588 KB	Output is correct
67	Correct	709 ms	512588 KB	Output is correct
68	Correct	1761 ms	512588 KB	Output is correct
69	Correct	2025 ms	512588 KB	Output is correct
70	Correct	2076 ms	512588 KB	Output is correct
71	Correct	6177 ms	512588 KB	Output is correct
72	Correct	6571 ms	512588 KB	Output is correct
73	Correct	7869 ms	512588 KB	Output is correct
74	Correct	7530 ms	512588 KB	Output is correct
75	Correct	7515 ms	512588 KB	Output is correct
76	Correct	7272 ms	512588 KB	Output is correct
77	Correct	7151 ms	512588 KB	Output is correct
78	Correct	7100 ms	512588 KB	Output is correct
79	Correct	7481 ms	512588 KB	Output is correct
80	Correct	7926 ms	512588 KB	Output is correct
81	Correct	7900 ms	512588 KB	Output is correct
82	Correct	7667 ms	512588 KB	Output is correct
83	Correct	9782 ms	512588 KB	Output is correct
84	Correct	8649 ms	532032 KB	Output is correct
85	Correct	4035 ms	532032 KB	Output is correct

답안 #60973

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 38.0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
38.0 / 38.0