QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#684838	#7502. Painting the Roads	tarjen	AC ✓	103ms	195768kb	C++20	1.6kb	2024-10-28 16:09:10	2024-10-28 16:09:11

Judging History

你现在查看的是最新测评结果

[2024-10-28 16:09:11]
评测

测评结果：AC
用时：103ms
内存：195768kb

查看

[2024-10-28 16:09:10]
提交

answer

#include <bits/stdc++.h>
using namespace std;
struct info{
    int to,l,c;
};
void gmin(int &x,int y){
    if(y<x)x=y;
}
const int inf=1e9;
int solve()
{
    int n,m;cin>>n>>m;
    vector<vector<info>> ve(n+1);
    for(int i=1;i<n;i++){
        int x,y,l,c;
        cin>>x>>y>>l>>c;
        ve[x].push_back(info{y,l,c});
        ve[y].push_back(info{x,l,c});
    }  
    vector<int>mx(n+1,0),mi(n+1,-1);
    for(int i=1;i<=m;i++){
        int x;cin>>x;
        mx[x]++;
    }
    vector<vector<int>>dp(n+1,vector<int>(m+n+1,inf));
    function<void(int,int)> dfs = [&](int x,int h){
        for(int i=mi[x];i<=mx[x];i++)dp[x][i+n]=0;
        for(auto [it,l,c]:ve[x])if(it!=h){
            // cout<<"to="<<it<<" l="<<l<<" c="<<c<<endl;
            dfs(it,x);
            vector<int> dp2(n+m+1,inf);
            for(int i=mi[x];i<=mx[x];i++){
                for(int j=mi[it];j<=mx[it];j++)if((j%2+2)%2==c){
                    gmin(dp2[i+j+n],dp[x][i+n]+dp[it][j+n]+abs(j)*l);
                }
            }
            mi[x]+=mi[it],mx[x]+=mx[it];
            dp[x]=move(dp2);
            // cout<<"x="<<x<<" to="<<it<<" mi="<<mi[x]<<" mx="<<mx[x]<<endl;
            // for(int i=mi[x];i<=mx[x];i++)cout<<dp[x][i+n]<<" ";;cout<<endl;
        }
       
    };
    dfs(1,-1);
    if(dp[1][n]>=inf)return -1;
    return dp[1][n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;while(T--)cout<<solve()<<"\n";
}

/*
1
10 5
1 2 10 1
2 3 3 1
3 4 4 0
4 5 4 1
5 6 2 1
2 7 8 0
2 8 9 1
4 9 1 0
1 10 4 0
10 10 2 1 8
*/

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3568kb

input:

5
3 2
1 2 1 1
2 3 2 1
1 3
4 2
1 2 3 1
2 3 1 0
3 4 4 1
1 2
5 4
1 2 3 0
2 3 1 1
3 4 2 0
4 5 2 1
1 1 1 1
5 2
1 2 2 1
1 3 3 0
1 5 2 1
3 4 1 1
1 2
10 5
1 2 10 1
2 3 3 1
3 4 4 0
4 5 4 1
5 6 2 1
2 7 8 0
2 8 9 1
4 9 1 0
1 10 4 0
10 10 2 1 8

output:

result:

ok 5 number(s): "3 9 21 -1 42"

Test #2:

score: 0

Accepted

time: 2ms

memory: 3564kb

input:

output:

result:

ok 1000 numbers

Test #3:

score: 0

Accepted

time: 2ms

memory: 3576kb

input:

250
20 10
1 2 10 1
1 3 3 1
2 4 6 0
4 5 8 0
2 6 5 0
4 7 1 1
1 8 6 0
4 9 2 1
3 10 9 1
3 11 1 0
6 12 10 0
6 13 8 0
13 14 7 0
14 15 10 1
1 16 4 0
12 17 2 0
17 18 8 1
18 19 3 0
2 20 4 1
15 14 20 20 9 17 4 4 13 13
20 6
1 2 4 1
1 3 10 1
2 4 10 1
3 5 1 1
2 6 6 0
4 7 5 1
3 8 8 1
7 9 7 0
6 10 3 1
6 11 4 1
8 1...

output:

result:

ok 250 numbers

Test #4:

score: 0

Accepted

time: 3ms

memory: 3628kb

input:

output:

result:

ok 100 numbers

Test #5:

score: 0

Accepted

time: 7ms

memory: 5684kb

input:

output:

result:

ok 10 numbers

Test #6:

score: 0

Accepted

time: 4ms

memory: 5824kb

input:

output:

result:

ok 10 numbers

Test #7:

score: 0

Accepted

time: 12ms

memory: 5768kb

input:

output:

result:

ok 10 numbers

Test #8:

score: 0

Accepted

time: 32ms

memory: 38732kb

input:

output:

-1
-1

result:

ok 2 number(s): "-1 -1"

Test #9:

score: 0

Accepted

time: 42ms

memory: 50332kb

input:

output:

6761
8789

result:

ok 2 number(s): "6761 8789"

Test #10:

score: 0

Accepted

time: 49ms

memory: 69052kb

input:

output:

6858
-1

result:

ok 2 number(s): "6858 -1"

Test #11:

score: 0

Accepted

time: 59ms

memory: 57432kb

input:

output:

6616
7292

result:

ok 2 number(s): "6616 7292"

Test #12:

score: 0

Accepted

time: 67ms

memory: 142468kb

input:

output:

result:

ok 1 number(s): "18174"

Test #13:

score: 0

Accepted

time: 56ms

memory: 133016kb

input:

1
5000 1616
1 2 3 1
1 3 4 0
3 4 2 0
3 5 4 0
4 6 5 0
4 7 4 0
3 8 1 0
5 9 2 0
3 10 5 0
1 11 5 1
4 12 2 0
3 13 2 1
4 14 5 0
4 15 4 0
1 16 1 0
1 17 5 0
4 18 6 0
4 19 4 0
4 20 5 0
2 21 2 0
1 22 6 1
3 23 4 0
2 24 4 1
3 25 8 0
4 26 2 1
4 27 6 0
2 28 7 1
2 29 1 1
1 30 9 1
1 31 7 0
1 32 4 0
4 33 5 0
5 34 6 0...

output:

result:

ok 1 number(s): "9970"

Test #14:

score: 0

Accepted

time: 44ms

memory: 114796kb

input:

output:

result:

ok 1 number(s): "5981"

Test #15:

score: 0

Accepted

time: 58ms

memory: 135080kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0

Accepted

time: 71ms

memory: 170692kb

input:

output:

result:

ok 1 number(s): "20709"

Test #17:

score: 0

Accepted

time: 78ms

memory: 195768kb

input:

output:

result:

ok 1 number(s): "14832"

Test #18:

score: 0

Accepted

time: 76ms

memory: 169188kb

input:

output:

result:

ok 1 number(s): "12769"

Test #19:

score: 0

Accepted

time: 74ms

memory: 155144kb

input:

output:

result:

ok 1 number(s): "11987"

Test #20:

score: 0

Accepted

time: 79ms

memory: 180968kb

input:

output:

result:

ok 1 number(s): "13461"

Test #21:

score: 0

Accepted

time: 83ms

memory: 178612kb

input:

output:

result:

ok 1 number(s): "15399"

Test #22:

score: 0

Accepted

time: 87ms

memory: 191976kb

input:

output:

result:

ok 1 number(s): "13750"

Test #23:

score: 0

Accepted

time: 68ms

memory: 167076kb

input:

output:

result:

ok 1 number(s): "12984"

Test #24:

score: 0

Accepted

time: 40ms

memory: 102080kb

input:

output:

result:

ok 1 number(s): "439"

Test #25:

score: 0

Accepted

time: 103ms

memory: 194532kb

input:

output:

result:

ok 1 number(s): "15533"

Test #26:

score: 0

Accepted

time: 48ms

memory: 128280kb

input:

output:

result:

ok 1 number(s): "8937"

Test #27:

score: 0

Accepted

time: 52ms

memory: 139524kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #28:

score: 0

Accepted

time: 97ms

memory: 187356kb

input:

output:

result:

ok 1 number(s): "13800"

Test #29:

score: 0

Accepted

time: 40ms

memory: 112972kb

input:

1
5000 571
1 2 7 1
1 3 9 0
1 4 5 1
4 5 8 1
2 6 1 1
2 7 5 0
5 8 6 1
5 9 9 0
8 10 6 1
6 11 5 1
8 12 5 0
10 13 5 1
11 14 6 1
12 15 8 0
13 16 8 1
13 17 5 0
14 18 6 0
14 19 9 0
17 20 4 0
17 21 5 0
17 22 8 0
18 23 2 0
23 24 9 0
24 25 2 0
21 26 7 0
24 27 7 0
27 28 7 1
27 29 2 1
26 30 8 0
30 31 5 0
27 32 8 ...

output:

result:

ok 1 number(s): "45838"

Test #30:

score: 0

Accepted

time: 43ms

memory: 112112kb

input:

output:

result:

ok 1 number(s): "25924"

Test #31:

score: 0

Accepted

time: 83ms

memory: 166468kb

input:

output:

result:

ok 1 number(s): "12327"

Test #32:

score: 0

Accepted

time: 18ms

memory: 25788kb

input:

output:

result:

ok 11 numbers

Test #33:

score: 0

Accepted

time: 48ms

memory: 70360kb

input:

output:

result:

ok 5 number(s): "8836 1053 4019 3 -1"

Test #34:

score: 0

Accepted

time: 75ms

memory: 129756kb

input:

output:

result:

ok 7 numbers

Test #35:

score: 0

Accepted

time: 25ms

memory: 42556kb

input:

output:

result:

ok 8 numbers

Test #36:

score: 0

Accepted

time: 43ms

memory: 104848kb

input:

6
4878 424
1 2 3 1
2 3 10 1
3 4 2 1
3 5 9 1
4 6 7 0
4 7 7 0
5 8 5 0
4 9 2 1
2 10 4 0
3 11 7 1
2 12 9 1
1 13 4 0
5 14 3 0
3 15 7 0
4 16 8 0
4 17 6 0
4 18 9 0
3 19 1 0
1 20 3 0
2 21 7 1
5 22 5 0
2 23 6 0
3 24 4 0
2 25 3 0
1 26 7 0
5 27 8 1
1 28 3 0
5 29 3 0
1 30 6 0
2 31 4 0
4 32 1 0
3 33 1 0
2 34 4 1...

output:

result:

ok 6 numbers

Test #37:

score: 0

Accepted

time: 52ms

memory: 103104kb

input:

output:

result:

ok 4 number(s): "8810 1090 672 6"

Test #38:

score: 0

Accepted

time: 54ms

memory: 100864kb

input:

output:

result:

ok 6 numbers

Test #39:

score: 0

Accepted

time: 65ms

memory: 131384kb

input:

output:

result:

ok 4 number(s): "10827 197 301 591"

Test #40:

score: 0

Accepted

time: 74ms

memory: 132860kb

input:

output:

result:

ok 5 number(s): "16879 553 185 147 9"

Test #41:

score: 0

Accepted

time: 27ms

memory: 38408kb

input:

output:

result:

ok 7 numbers

Test #42:

score: 0

Accepted

time: 35ms

memory: 38500kb

input:

output:

result:

ok 10 numbers

Test #43:

score: 0

Accepted

time: 41ms

memory: 76640kb

input:

output:

result:

ok 7 numbers

Test #44:

score: 0

Accepted

time: 16ms

memory: 16116kb

input:

output:

result:

ok 7 numbers

Test #45:

score: 0

Accepted

time: 48ms

memory: 64492kb

input:

output:

result:

ok 7 numbers

Test #46:

score: 0

Accepted

time: 67ms

memory: 90696kb

input:

output:

result:

ok 8 numbers

Test #47:

score: 0

Accepted

time: 54ms

memory: 116168kb

input:

output:

result:

ok 6 numbers

Test #48:

score: 0

Accepted

time: 23ms

memory: 25036kb

input:

output:

result:

ok 6 numbers

Test #49:

score: 0

Accepted

time: 36ms

memory: 40788kb

input:

output:

result:

ok 6 numbers

Test #50:

score: 0

Accepted

time: 32ms

memory: 68288kb

input:

output:

result:

ok 6 numbers

Test #51:

score: 0

Accepted

time: 30ms

memory: 32700kb

input:

output:

result:

ok 9 numbers