QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #91988 | #5102. Dungeon Crawler | Serdahsufyan | TL | 172ms | 45072kb | Java8 | 10.7kb | 2023-03-30 06:41:20 | 2023-03-30 06:41:24 |
Judging History
answer
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;
/**
*
* @author HP
*/
public class CodeJamDungion {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner s=new Scanner(System.in);
int gSize=s.nextInt();
int sSize=s.nextInt();
GraphNode[] nodeArr=new GraphNode[gSize+1];
for (int i = 1; i < gSize+1; i++) {
nodeArr[i]=new GraphNode(i);
}
for (int i = 1; i < gSize; i++) {
int sNode=s.nextInt();
int eNode=s.nextInt();
int weight=s.nextInt();
nodeArr[sNode].adjList.add(new Pair(nodeArr[eNode],weight));
nodeArr[eNode].adjList.add(new Pair(nodeArr[sNode],weight));
}
for (int m = 0; m < sSize; m++) {
for (int i = 1; i < nodeArr.length; i++) {nodeArr[i].parent=null;nodeArr[i].dist=0;nodeArr[i].sDist=0;nodeArr[i].isKP=false;nodeArr[i].isTP=false;}
int start=s.nextInt();
int key=s.nextInt();
int trap=s.nextInt();
Graph g=new Graph(nodeArr[start],nodeArr[key],nodeArr[trap],gSize);
if(g.isImpossible())System.out.println("impossible");
else if(g.isEasy()){
int sumOfEdges=0;
int max=0;
for (int i = 1; i < nodeArr.length; i++) {
for (int j = 0; j < nodeArr[i].adjList.size(); j++) {
sumOfEdges+=nodeArr[i].adjList.get(j).weight;
}
}
for (int i = 1; i < nodeArr.length; i++) {
if(nodeArr[i].dist>max)max=nodeArr[i].dist;
}
System.out.println(sumOfEdges-max);
}
else {
int maxN=g.NKBFS();
int sol1=0;
int sumOfEdges=0;
for (int i = 1; i < nodeArr.length; i++) {
for (int j = 0; j < nodeArr[i].adjList.size(); j++) {
sumOfEdges+=nodeArr[i].adjList.get(j).weight;
}
}
sol1=sumOfEdges-maxN;
int a=g.sDistBFS();
//System.out.println("sdist: "+a);
int sol2=sumOfEdges+a;
System.out.println(Math.min(sol2, sol1));
}
}}
}
class Graph {
int size;
GraphNode start,hKey,trap,fP;
public Graph(GraphNode s,GraphNode k,GraphNode t,int size){
start=s;
hKey=k;
trap=t;
this.size=size;
this.BFS();
fP=this.pOfK();
}
public void clear(){
}
public void BFS()
{
GraphNode s=start;
s.dist=0;
// Mark all the vertices as not visited(By default
// set as false)
boolean visited[] = new boolean[size];
// Create a queue for BFS
LinkedList<GraphNode> queue
= new LinkedList<GraphNode>();
// Mark the current node as visited and enqueue it
visited[s.NodeNum-1] = true;
queue.add(s);
while (queue.size() != 0) {
// Dequeue a vertex from queue and print it
s = queue.poll();
// Get all adjacent vertices of the dequeued
// vertex s If a adjacent has not been visited,
// then mark it visited and enqueue it
ListIterator<Pair> i = s.adjList.listIterator();
while (i.hasNext()) {
Pair m = i.next();
GraphNode n=m.n;
if (!visited[n.NodeNum-1]) {
visited[n.NodeNum-1] = true;
n.parent=s;
n.dist=s.dist+m.weight;
queue.add(n);
}
}
}
}
public int KBFS()
{
GraphNode s=hKey;
// Mark all the vertices as not visited(By default
// set as false)
boolean visited[] = new boolean[size];
// Create a queue for BFS
LinkedList<GraphNode> queue
= new LinkedList<GraphNode>();
// Mark the current node as visited and enqueue it
visited[s.NodeNum-1] = true;
visited[s.parent.NodeNum-1]=true;
queue.add(s);
int maxFromKey=s.dist;
while (queue.size() != 0) {
// Dequeue a vertex from queue and print it
s = queue.poll();
// Get all adjacent vertices of the dequeued
// vertex s If a adjacent has not been visited,
// then mark it visited and enqueue it
ListIterator<Pair> i = s.adjList.listIterator();
while (i.hasNext()) {
Pair m = i.next();
GraphNode n=m.n;
if (!visited[n.NodeNum-1]) {
visited[n.NodeNum-1] = true;
if(n.dist>maxFromKey)maxFromKey=n.dist;
queue.add(n);
}
}
}
return maxFromKey;
}
public int NKBFS()
{
GraphNode s=start;
// Mark all the vertices as not visited(By default
// set as false)
boolean visited[] = new boolean[size];
// Create a queue for BFS
LinkedList<GraphNode> queue
= new LinkedList<GraphNode>();
// Mark the current node as visited and enqueue it
visited[s.NodeNum-1] = true;
for (int i = 0; i < s.adjList.size(); i++) {
if(s.adjList.get(i).n.isKP&&!s.adjList.get(i).n.isTP)visited[s.adjList.get(i).n.NodeNum-1]=true;
}
queue.add(s);
int maxFromNonKey=s.dist;
while (queue.size() != 0) {
// Dequeue a vertex from queue and print it
s = queue.poll();
// Get all adjacent vertices of the dequeued
// vertex s If a adjacent has not been visited,
// then mark it visited and enqueue it
ListIterator<Pair> i = s.adjList.listIterator();
while (i.hasNext()) {
Pair m = i.next();
GraphNode n=m.n;
if (!visited[n.NodeNum-1]&&(!n.isKP||n.isTP)) {
visited[n.NodeNum-1] = true;
if(n.dist>maxFromNonKey)maxFromNonKey=n.dist;
queue.add(n);
}
}
}
return maxFromNonKey;
}
public int sDistBFS()
{
GraphNode s=fP;
int ss=s.dist;
//System.out.println("fp "+fP.NodeNum);
// Mark all the vertices as not visited(By default
// set as false)
boolean visited[] = new boolean[size];
// Create a queue for BFS
LinkedList<GraphNode> queue
= new LinkedList<GraphNode>();
// Mark the current node as visited and enqueue it
visited[s.NodeNum-1] = true;
queue.add(s);
for (int i = 0; i < s.adjList.size(); i++) {
if(!s.adjList.get(i).n.isKP||(s.adjList.get(i).n.isKP&&s.adjList.get(i).n.isTP))visited[s.adjList.get(i).n.NodeNum-1]=true;
}
int minSDist=999999999;
while (queue.size() != 0) {
// Dequeue a vertex from queue and print it
s = queue.poll();
// Get all adjacent vertices of the dequeued
// vertex s If a adjacent has not been visited,
// then mark it visited and enqueue it
ListIterator<Pair> i = s.adjList.listIterator();
while (i.hasNext()) {
Pair m = i.next();
GraphNode n=m.n;
//System.out.println("Before: Node: "+n.NodeNum+" dist: "+n.dist+" SDIST:"+ n.sDist+" Visited:"+visited[n.NodeNum-1]);
if (!visited[n.NodeNum-1]&&!n.isKP) {
visited[n.NodeNum-1] = true;
if(!n.parent.isKP){
n.sDist=n.parent.sDist-m.weight;}
else{n.sDist=n.parent.dist-m.weight;}
minSDist=Math.min(minSDist,n.sDist);
queue.add(n);
}
else if(!visited[n.NodeNum-1]){
visited[n.NodeNum-1] = true;
queue.add(n);
}
//System.out.println("Before: Node: "+n.NodeNum+" dist: "+n.dist+" SDIST:"+ n.sDist+" Visited:"+visited[n.NodeNum-1]);
}
}
//System.out.println("ss is:"+ss+" , mindist is:"+minSDist);
return minSDist-2*ss;
}
GraphNode pOfK(){
GraphNode k=hKey;
hKey.isKP=true;
while(k.parent!=null){
k=k.parent;
k.isKP=true; }
GraphNode t=trap;
trap.isTP=true;
while(t.parent!=null){
t=t.parent;
t.isTP=true; }
GraphNode k1=hKey;
GraphNode kt=hKey;
boolean stch=true;
while(k1!=null){
if(k1.isTP){if(stch){kt=k1;stch=false;}
}
k1=k1.parent;
}
return kt;
}
boolean isImpossible(){
GraphNode s=start;
GraphNode k=hKey;
GraphNode t=trap;
boolean Impossible=false;
GraphNode n=k.parent;
while(n!=null){
if(n==t)Impossible=true;
n=n.parent;
}
return Impossible;
}
boolean isEasy(){
GraphNode s=start;
GraphNode k=hKey;
GraphNode t=trap;
boolean Easy=false;
GraphNode n=t.parent;
while(n!=null){
if(n==k)Easy=true;
n=n.parent;
}
return Easy;
}
}
class GraphNode {
int NodeNum;
ArrayList<Pair> adjList;
GraphNode parent=null;
int dist=999999999;
boolean isKP=false;
boolean isTP=false;
int sDist=0;
public GraphNode(int num){
NodeNum=num;
adjList=new ArrayList<Pair>();
}
}
class Pair{
GraphNode n;
Integer weight;
public Pair(GraphNode n,Integer weight){
this.n=n;
this.weight=weight;
}
}
//
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 90ms
memory: 37340kb
input:
22 5 1 2 7 2 3 5 3 4 8 3 6 6 3 7 3 2 5 6 5 8 2 8 9 11 2 10 16 1 11 12 11 12 4 11 13 9 1 14 25 14 15 4 15 16 5 15 17 6 15 18 1 15 19 8 14 20 7 20 21 9 20 22 17 1 19 9 1 9 19 1 8 9 1 9 8 2 22 11
output:
316 293 293 impossible 314
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 172ms
memory: 45072kb
input:
100 100 1 2 289384 2 3 930887 2 4 692778 4 5 636916 4 6 747794 4 7 238336 4 8 885387 8 9 760493 8 10 516650 8 11 641422 8 12 202363 8 13 490028 8 14 368691 8 15 520060 8 16 897764 16 17 513927 16 18 180541 16 19 383427 16 20 89173 16 21 455737 16 22 5212 16 23 595369 16 24 702568 16 25 956430 16 26 ...
output:
103526917 103484292 106288816 104379596 104405611 104775512 105434682 105291604 103838430 105371370 104677980 104175650 105894571 104509242 103971939 105376499 105223283 104153426 105082245 105413188 104130613 104800548 106846555 104138329 103769253 105456754 104044745 104385328 106973740 105460460 ...
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 129ms
memory: 38820kb
input:
10 6 1 2 4 2 3 7 2 4 8 4 5 6 4 6 4 4 7 6 4 8 7 8 9 3 8 10 10 3 8 1 10 4 7 1 7 3 7 2 9 8 10 3 4 1 6
output:
99 78 97 87 88 93
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 96ms
memory: 36872kb
input:
10 9 9 2 5 9 1 6 9 4 97 9 7 2 9 8 42 9 10 11 9 6 77 9 3 14 9 5 9 4 7 10 7 3 8 8 7 9 1 4 8 10 7 4 7 1 2 10 1 5 10 7 2 8 4 10
output:
352 427 impossible 443 418 427 418 418 407
result:
ok 9 lines
Test #5:
score: 0
Accepted
time: 104ms
memory: 38928kb
input:
9 9 2 3 48 9 5 31 7 3 97 4 3 16 1 7 24 5 3 82 8 2 51 6 4 33 1 2 8 3 6 8 1 6 3 9 5 6 2 6 4 5 6 1 9 6 4 2 8 9 4 9 2
output:
530 643 impossible 530 impossible 561 impossible 595 627
result:
ok 9 lines
Test #6:
score: 0
Accepted
time: 111ms
memory: 37784kb
input:
8 9 1 7 51 7 6 86 2 3 62 8 4 72 5 6 17 4 1 75 3 1 41 2 3 7 5 8 4 6 1 3 8 6 2 4 2 7 8 5 6 2 1 5 7 1 6 6 7 8
output:
551 impossible 524 558 579 impossible 551 705 524
result:
ok 9 lines
Test #7:
score: 0
Accepted
time: 124ms
memory: 36960kb
input:
9 9 5 4 13 9 2 10 1 9 25 7 6 34 4 2 77 3 8 67 8 1 57 6 9 100 6 4 1 4 1 7 3 2 9 4 9 7 7 9 3 6 2 1 2 8 4 8 6 2 6 5 9
output:
517 545 impossible 530 483 517 642 584 impossible
result:
ok 9 lines
Test #8:
score: 0
Accepted
time: 111ms
memory: 36852kb
input:
10 10 2 4 26 9 8 39 4 5 88 6 3 70 7 6 7 10 4 41 8 3 57 1 6 15 5 6 9 2 8 6 3 9 1 5 7 8 4 7 8 7 6 4 2 7 3 6 8 2 5 4 10 4 8 9 1 5 9
output:
impossible 496 529 441 531 415 566 529 441 523
result:
ok 10 lines
Test #9:
score: 0
Accepted
time: 103ms
memory: 37184kb
input:
10 9 3 2 6 2 1 18 8 1 44 1 9 42 6 3 72 10 8 46 7 10 93 5 3 11 4 10 13 7 3 1 8 2 5 7 5 4 5 10 8 3 1 4 6 4 3 10 1 6 5 10 8 2 10 4
output:
impossible 550 584 impossible 483 impossible 504 impossible 489
result:
ok 9 lines
Test #10:
score: -100
Time Limit Exceeded
input:
2000 199998 126 244 481188299 718 1159 740107180 1327 1250 248943862 977 1092 780169400 826 27 932696654 1668 638 478193038 229 174 176675890 1251 646 843918836 102 1973 593920932 236 218 165399894 760 151 890198591 232 502 10739184 1961 1409 45917915 548 1840 974742709 1096 630 280975617 1110 1048 ...
output:
460286122 impossible 458590962 457433555 457270452 impossible 462949634 458737618 459362375 459376917 impossible impossible 471834165 impossible impossible impossible 456848198 461352945 459457051 461516000 457063539 460380279 impossible 459686542 impossible 458793209 457491809 457219644 impossible ...