可能赢了
可能没赢
UPD:赢了，爽啊。。谁知道第二名多少分？
比赛体验一般。没人回答问题，评测queue长达15分钟。
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>string to_string(pair<A, B> p);template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p);template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p);string to_string(const string& s) { return '"' + s + '"';}string to_string(const char* s) { return to_string((string) s);}string to_string(bool b) { return (b ? "true" : "false");}string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res;}template <size_t N>string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res;}template <typename A>string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res;}template <typename A, typename B>string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";}template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...);}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,int> pdi;
template<typename T> void read(T &x){
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
int n,l,m,cap,vc[2020];
struct edge{
int to,tc;
double cost;
};
vector<edge> edges[2020];
double md[10000010];
int fr[10000010];
int main() {
read(n,l,m,cap);
cout<<setprecision(6)<<fixed;
for(int i=1;i<=l;i++){
read(vc[i]);
}
for(int i=1;i<=m;i++){
int fr,to,co;
double prob;
scanf("%d%d%lf%d",&fr,&to,&prob,&co);
if(prob!=1) edges[fr].PB({to,co,-log(1-prob)});
else edges[fr].PB({to,co,1e8});
}
for(int i=0;i<10000010;i++)md[i] = 1e18;
priority_queue<pdi,vector<pdi>,greater<pdi>> Pq;
Pq.push(MP(0.0,0));
md[0] = 0;
while(!Pq.empty()){
pdi C = Pq.top();Pq.pop();
if(C.F>md[C.S])continue;
int a = (C.S>5000000),b = C.S-(a?5000000:0),c = b%2001,d = b/2001;
if(a && d == 0){
vector<int> V;
int ct = C.S;
int id = 0;
while(ct!=0){
int C = (ct%5000000)/2001;
if(V.size() && V.back() == C){
id = C;
}else{
V.PB(C);
}
ct = fr[ct];
}
V.PB(ct);
reverse(all(V));
cout<<id<<endl;
cout<<c<<endl;
cout<<1.0-exp(-C.F)<<endl;
for(int i=0;i<V.size();i++){
cout<<V[i]<<" \n"[i == V.size()-1];
}
return 0;
}
if(!a && d<=l && d>=1 && c+vc[d]<=cap){
int tgt = C.S+5000000+vc[d];
if(md[tgt]>C.F){
md[tgt] = C.F;
fr[tgt] = C.S;
Pq.push(MP(C.F,tgt));
}
}
for(auto ct:edges[d]){
if(c+ct.tc>cap)continue;
int tgt = ct.to*2001+c+ct.tc+(a?5000000:0);
if(md[tgt]>C.F+ct.cost){
md[tgt] = C.F+ct.cost;
fr[tgt] = C.S;
Pq.push(MP(C.F+ct.cost,tgt));
}
}
}
return 0;
}#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
template <typename A, typename B>string to_string(pair<A, B> p);template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p);template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p);string to_string(const string& s) { return '"' + s + '"';}string to_string(const char* s) { return to_string((string) s);}string to_string(bool b) { return (b ? "true" : "false");}string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res;}template <size_t N>string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res;}template <typename A>string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res;}template <typename A, typename B>string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";}template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...);}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void read(T &x){
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
string Fsys[18000000];
int Fcnt = 0;
int filemp[5050][5050];
bool fileown[5050][5050];
bool cmp[5050][5050];
map<string,int> Files,Commits;
string Fname[5050];
char op[150],name[150],name1[150],name2[150],File[400];
int N,offset,len;
int wcmt = 0,wcac = 1,cac_emp = 1;
void Mgtline(char *Tgt){
while(1){
char ch= getchar();
if(ch == '\n'){
*Tgt = 0;
return;
}else{
*Tgt = ch;
Tgt++;
}
}
}
void make_cac(){
if(!cac_emp)return;
cac_emp = 0;
int T = Files.size();
for(int i=1;i<=T;i++){
filemp[wcac][i] = filemp[wcmt][i];
}
}
int main() {
read(N);
for(int opn = 1;opn<=N;opn++){
scanf("%s",op);
if(op[0] == 'w'){
make_cac();
scanf("%s",name);
read(offset,len);
string Sname(name);
if(!Files.count(Sname)){
int cnid = Files.size()+1;
Files[Sname] = cnid;
Fname[cnid] = Sname;
for(int j=1;j<cnid;j++){
cmp[j][cnid] = Fname[j]>Fname[cnid];
cmp[cnid][j] = !cmp[j][cnid];
}
}
int FNid = Files[Sname];
int Fid = filemp[wcac][FNid];
if(Fid<=0){
Fid = ++Fcnt;
filemp[wcac][FNid] = Fid;
fileown[wcac][FNid] = 1;
}
if(!fileown[wcac][FNid]){
Fid = ++Fcnt;
Fsys[Fid] = Fsys[filemp[wcac][FNid]];
filemp[wcac][FNid] = Fid;
fileown[wcac][FNid] = 1;
}
if(Fsys[Fid].length()<offset+len)Fsys[Fid].resize(offset+len,'.');
Mgtline(File);
for(int i=0;i<len;i++)Fsys[Fid][offset+i] = File[i];
}
if(op[0] == 'r'){
scanf("%s",name);
read(offset,len);
string Sname(name);
if(!Files.count(Sname)){
for(int i=0;i<len;i++)putchar('.');
putchar('\n');
continue;
}
int FNid = Files[Sname];
int Fid = filemp[wcac][FNid]?filemp[wcac][FNid]:filemp[wcmt][FNid];
if(Fid<=0){
for(int i=0;i<len;i++)putchar('.');
putchar('\n');
continue;
}
for(int i=0;i<len;i++)putchar((offset+i)<Fsys[Fid].size()?Fsys[Fid][offset+i]:'.');
putchar('\n');
}
if(op[0] == 'u'){
scanf("%s",name);
string Sname(name);
if(!Files.count(Sname)){
continue;
}
int FNid = Files[Sname];
int Fid = filemp[wcac][FNid]?filemp[wcac][FNid]:filemp[wcmt][FNid];
if(Fid<=0) continue;
make_cac();
++Fcnt;
filemp[wcac][FNid] = -Fcnt;
}
if(op[0] == 'l'){
int t = Files.size();
int cnt = 0,mi,mx;
for(int i=1;i<=t;i++){
int Fid = filemp[wcac][i]?filemp[wcac][i]:filemp[wcmt][i];
if(Fid<=0) continue;
cnt+=1;
if(cnt == 1){
mi = mx = i;
}else{
if(cmp[mi][i])mi = i;
if(cmp[i][mx])mx = i;
}
}
if(cnt == 0)cout<<"0\n";
else{
cout<<cnt<<' '<<Fname[mi]<<' '<<Fname[mx]<<"\n";
}
}
if(op[0] == 'c' && op[1] == 'o'){
scanf("%s",name);
string Sname(name);
if(Commits.count(Sname) || cac_emp){
debug("Commit Skipped");
continue;
}
Commits[Sname] = wcac;
wcmt = wcac;
wcac = Commits.size()+1;
cac_emp = 1;
}
if(op[0] == 'c' && op[1] == 'h'){
scanf("%s",name);
string Sname(name);
if(!Commits.count(Sname) || !cac_emp){
debug("Checkout Skipped");
continue;
}
wcmt = Commits[Sname];
}
if(op[0] == 'm'){
scanf("%s%s",name1,name2);
string S1(name1),S2(name2);
if(Commits.count(S2) || !Commits.count(S1) || Commits[S1] == wcmt || !cac_emp){
debug("Merge Skipped");
continue;
}
int wcmt2 = Commits[S1];
int T = Files.size();
for(int i=1;i<=T;i++){
if(abs(filemp[wcmt][i])>abs(filemp[wcmt2][i])) filemp[wcac][i] = filemp[wcmt][i];
else filemp[wcac][i] = filemp[wcmt2][i];
}
Commits[S2] = wcac;
wcmt = wcac;
wcac = Commits.size()+1;
cac_emp = 1;
}
}
return 0;
}#include "gc.h"
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>string to_string(pair<A, B> p);template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p);template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p);string to_string(const string& s) { return '"' + s + '"';}string to_string(const char* s) { return to_string((string) s);}string to_string(bool b) { return (b ? "true" : "false");}string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res;}template <size_t N>string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res;}template <typename A>string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res;}template <typename A, typename B>string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";}template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...);}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void read(T &x){
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
using namespace std;
bool vis[1024] = {0};
void gc(unsigned char *mem) {
unsigned char *opt = mem;
static unsigned char nmem[1024*1024*64];
int Rn = *((int*)mem);
queue<int> Q2;
debug(Rn);
for(int i=0;i<Rn;i++){
int pt = ((int*)mem)[i+1];
debug(pt);
Q2.push(pt);
}
mem+=4*(Rn+1);
int Tn = *((int*)mem);
debug(Tn);
mem+=4;
vector<int> Tmap[1024][4];
bool vis[1024] = {0};
int rewire[1024] = {0};
for(int i=0;i<Tn;i++){
int tnt = *((int*)mem);
debug(tnt);
mem+=4;
int cp = 0;
for(int j=0;j<tnt;j++){
debug((int)mem[j],cp);
if(mem[j] == 0){
Tmap[i][mem[j]].PB(cp);
cp+=1;
}
if(mem[j] == 1){
if(cp&1)cp+=1;
Tmap[i][mem[j]].PB(cp);
cp+=2;
}
if(mem[j] >= 2){
if(cp&3)cp+=4-(cp&3);
Tmap[i][mem[j]].PB(cp);
cp+=4;
}
}
mem+=tnt;
}
int Hl = *((int*)mem);
debug(Hl);
mem+=4;
unsigned char *old_heap = mem;
int sz = 0;
vector<int> wupd_pointers,wupd_clsname;
queue<int> Q;
while(!Q2.empty()){
int C = Q2.front();Q2.pop();
*((int*)(mem+C)) = *((int*)(mem+C))+2048;
Q.push(C);
}
while(!Q.empty()){
debug(Q.size());
int C = Q.front();Q.pop();
debug(1);
int typ = *((int*)(mem+C));
assert(typ<134217728);
typ = typ&2047;
vis[typ] = 1;
wupd_clsname.PB(sz);
*((int*)(nmem+sz)) = typ;
*((int*)(mem+C)) = sz+134217728;
unsigned char* cstr = mem+C+4;
sz+=4;
for(auto ct:Tmap[typ][0]){
nmem[sz] = cstr[ct];
sz+=1;
}
debug(2);
if(sz&1)sz+=1;
for(auto ct:Tmap[typ][1]){
nmem[sz] = cstr[ct];
nmem[sz+1] = cstr[ct+1];
sz+=2;
}
if(sz&3)sz+=1;
if(sz&3)sz+=1;
for(auto ct:Tmap[typ][2]){
*((int*)(nmem+sz)) = *((int*)(cstr+ct));
sz+=4;
}
debug(3);
for(auto ct:Tmap[typ][3]){
debug(ct);
debug(*((int*)(cstr+ct)));
int cv = *((int*)(cstr+ct)),cv2 = *((int*)(mem+cv));
debug(cv);
debug(cv2);
debug(sz);
if(cv == 1){
*((int*)(nmem+sz)) = 1;
sz+=4;
continue;
}
if(cv2&134217728) *((int*)(nmem+sz)) = cv2-134217728;
else{
wupd_pointers.PB(sz);
if(!(cv2&2048)){
*((int*)(mem+cv)) = cv2+2048;
Q.push(cv);
}
*((int*)(nmem+sz)) = cv;
}
sz+=4;
debug(cv,"end");
}
debug(1235);
}
debug(234);
for(auto ct:wupd_pointers){
int cv = *((int*)(nmem+ct));
int cv2 = *((int*)(mem+cv));
if(cv2&134217728) *((int*)(nmem+ct)) = cv2-134217728;
}
debug(235);
mem = opt;
int Rn2 = *((int*)mem);
for(int i=0;i<Rn2;i++){
((int*)mem)[i+1] = (*((int*)(old_heap+((int*)mem)[i+1])))-134217728;
}
debug(236);
mem+=4*(Rn+1);
int Tn2 = 0;
for(int i=0;i<1024;i++){
if(vis[i])rewire[i] = Tn2;
Tn2+=vis[i];
}
*((int*)mem) = Tn2;
mem+=4;
debug(237);
for(int i=0;i<Tn;i++){
if(!vis[i])continue;
int tnt = Tmap[i][0].size()+Tmap[i][1].size()+Tmap[i][2].size()+Tmap[i][3].size();
*((int*)mem) = tnt;
mem+=4;
for(int j=0;j<Tmap[i][0].size();j++)mem[j] = 0;
mem+=Tmap[i][0].size();
for(int j=0;j<Tmap[i][1].size();j++)mem[j] = 1;
mem+=Tmap[i][1].size();
for(int j=0;j<Tmap[i][2].size();j++)mem[j] = 2;
mem+=Tmap[i][2].size();
for(int j=0;j<Tmap[i][3].size();j++)mem[j] = 3;
mem+=Tmap[i][3].size();
}
debug(238);
for(auto ct:wupd_clsname){
*((int*)(nmem+ct)) = rewire[*((int*)(nmem+ct))];
}
*((int*)mem) = sz;
memcpy(mem+4,nmem,sz);
}
发表回复