| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1015745 |
2024-07-06T17:55:13 Z |
Taresu |
Robot (JOI21_ho_t4) |
C++11 |
|
129 ms |
22920 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define INF 0x7fffffff
#define MINF -0x7fffffff
#define MAX_VAL 0x7fffffffffffffff
#define pb push_back
#define sz(a) a.size()
#define mod 998244353
#define MOD 1000000007
#define f first
#define s second
#define sortv(a) sort(a.begin(), a.end())
#define rsortv(a) sort(a.rbegin(), a.rend())
#define ins insert
#define fr(i, a) for(long long int i=0;i<a;i++)
#define fr1(i, a) for(long long int i=1;i<=a;i++)
#define mem0(a) memset(a, 0, sizeof(a)) // a nome da matirz
#define mem1(a) memset(a, 1, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define memI(a) memset(a, 0x3f3f3f3f, sizeof(a))
#define formap(it, a) for(map<pipii, ll>::iterator it=a.begin();it!=a.end();it++)
#define forset(it, a) for(set<int>::iterator it=a.begin();it!=a.end();it++)
#define formset(it, a) for(multiset<int>::iterator it=a.begin();it!=a.end();it++)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>ordered_set;
typedef long long int ll;
typedef pair<ll, ll> pii;
typedef pair<ll, pair<ll, ll> > pipii;
typedef priority_queue<pipii, vector<pipii>, greater<pipii> > pqueue;
using Matrix = array<array<ll, 110>, 110>;
Matrix mul(Matrix a, Matrix b, ll m){
Matrix res;
fr(i, 110)
fr(j, 110)
res[i][j]=0x3f3f3f3f3f3f3f3f;
for (int i = 1; i < 101; i++) {
for (int j = 1; j < 101; j++) {
for (int k = 1; k < 101; k++) {
//res[i][j] += a[i][k] * b[k][j]; // multiplicaçao
//res[i][j] = min(res[i][j], a[i][k] + b[k][j]); // min sum distance
//res[i][j] %= m;
}
}
}
return res;
}
ll gcd(ll a, ll b){
return b==0 ? a : gcd(b, a%b);
}
ll lcm(ll a, ll b){
return (a*b)/gcd(a, b);
}
ll fexp(ll b, ll e, ll m){
if(e==0) return 1;
if(e==1) return b%m;
ll h=fexp(b, e/2, m);
if(e%2==0){
return (h*h)%m;
}else{
return (((h*h)%m)*b)%m;
}
}
Matrix indentityMatrix(int n){
Matrix id;
fr(i, n){
fr(j, n){
id[i][j]=0;
if(i==j)
id[i][j]=0x3f3f3f3f3f3f3f3f; // se for so multilicaçao 1 se min dist coloque o infinito
}
}
return id;
}
Matrix mexp(Matrix b, ll e, ll m){
if(e==0) return indentityMatrix(101); // a dependennder da operaçao mul a identidade mdua
if(e==1) return b;
Matrix h=mexp(b, e/2, m);
if(e%2==0){
return mul(h, h, m);
}else{
return mul(mul(h, h, m), b, m);
}
}
ll inv(ll x, ll m){
if (x <= 1) {
return x;
}
return m-m/x*inv(m % x, m)%m;
}
void irr(ll *a, ll *b){ //deixar primos entre si
ll gc=gcd(*a, *b);
*a/=gc;
*b/=gc;
}
ll divmod(ll num, ll den, ll m){
return (num*fexp(den, m-2, m))%m;
}
int setbits(int x){
return __builtin_popcount(x);
}
int lgb(ll x, ll b){
int ct=-1;
while(x>0){
ct++;
x/=b;
}
return ct+1;
}
struct vetor{
double x, y;
};
double norma(vetor a){
return sqrt(a.x*a.x+a.y*a.y);
}
double dotproduct(vetor a, vetor b){
return a.x*b.x+a.y*b.y;
}
double arg(vetor a, vetor b){
double ag=dotproduct(a, b)/(norma(a)*norma(b));
return -1*acos(ag);
}
vetor rotacionaarg(vetor v, double ang){
vetor r={v.x*cos(ang)-v.y*sin(ang), v.y*cos(ang)+v.x*sin(ang)};
return r;
}
///////////////SOLVE
//////////////////////////////////
////////////////////////
vector<pipii> g[100100];
ll dist[100100];
ll cordp[200100];
map<ll, multiset<ll> > cores;
bool processado[100100];
int coreli[100100];
bool onlyone(ll v, ll cor){
bool ans=0;
if(cores[v].find(cor)==cores[v].end()){ // was ekeiunter
return true;
}
cores[v].erase(cores[v].find(cor));
if(cores[v].find(cor)==cores[v].end())
ans=1;
cores[v].ins(cor);
return ans;
}
void solve(){
memset(processado, 0, sizeof(processado));
mem_1(coreli);
fr(i, 100100){
dist[i]=0x3f3f3f3f3f3f3f3f;
}
int n;
cin >> n;
int q;
cin >> q;
for(int i=0;i<q;i++){
ll a, b, c, d;
cin >> a >> b >> c >> d;
g[a].push_back({b, {d, i}});
g[b].push_back({a, {d, i}});
cores[a].ins(c);
cores[b].ins(c);
cordp[i]=c;
}
// djikstra begin
dist[1]=0;
priority_queue<pii, vector<pii>, greater<pii> > fila;
fila.push({0, 1});
while(true){
int davez=-1;
while(!fila.empty()){
int u=fila.top().s;
fila.pop();
if(!processado[u]){
processado[u]=1;
davez=u;
break;
}
}
if(davez==-1){
break;
}
if(coreli[davez]!=-1){
cores[davez].erase(coreli[davez]);
}
for(int i=0;i<sz(g[davez]);i++){
int olho=g[davez][i].f;
int peso=g[davez][i].s.f;
int pista=g[davez][i].s.s;
if(onlyone(davez, cordp[pista]))
peso=0;
if(dist[olho]>dist[davez]+peso){
if(peso!=0){
coreli[olho]=cordp[pista];
}
dist[olho]=dist[davez]+peso;
fila.push({dist[olho], olho});
}
}
}
if(dist[n]==0x3f3f3f3f3f3f3f3f) cout << "-1\n";
else cout << dist[n] << '\n';
//djikstra end
}
///////////////SOLVE
//////////////////////////////////
////////////////////////
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
/*/freopen("mootube.in","r",stdin);
freopen("mootube.out","w",stdout);/**/
int t=1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
Compilation message
Main.cpp:252:40: warning: "/*" within comment [-Wcomment]
252 | freopen("mootube.out","w",stdout);/**/
|
Main.cpp: In function 'void solve()':
Main.cpp:219:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
219 | for(int i=0;i<sz(g[davez]);i++){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
5468 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
22920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
5468 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
